【文章內(nèi)容簡(jiǎn)介】 ，或者說(shuō)， A中的元素 aij表示了結(jié)點(diǎn) vi和結(jié)點(diǎn) vj（ 0≤j≤n1）的鄰接關(guān)系，所以矩陣 A稱作 鄰接矩陣 。 無(wú)向圖及其鄰接矩陣 有向圖及其鄰接矩陣帶權(quán)圖及其鄰接矩陣 圖的鄰接表存儲(chǔ)結(jié)構(gòu) 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)是把圖的邊信息存儲(chǔ)在一個(gè) nn矩陣中，其中 n為圖中的結(jié)點(diǎn)個(gè)數(shù)。 有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) 鄰接矩陣圖類 ? 鄰接矩陣圖類 AdjMWGraph 的設(shè)計(jì)? 鄰接矩陣圖類 AdjMWGraph 的測(cè)試 圖的遍歷 圖的深度和廣度優(yōu)先遍歷算法 圖的遍歷算法設(shè)計(jì)需要考慮三個(gè)問(wèn)題： （ 1）圖的特點(diǎn)是沒(méi)有首尾之分，所以算法的參數(shù)要指定訪問(wèn)的第一個(gè)結(jié)點(diǎn)； （ 2）對(duì)圖的遍歷路徑有可能構(gòu)成一個(gè)回路，從而造成死循環(huán)，所以算法設(shè)計(jì)要考慮遍歷路徑可能出現(xiàn)的死循環(huán)問(wèn)題； （ 3）一個(gè)結(jié)點(diǎn)可能和若干個(gè)結(jié)點(diǎn)都是鄰接結(jié)點(diǎn)，要使一個(gè)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)按照某種次序被訪問(wèn)。1 圖的深度優(yōu)先遍歷算法 連通圖的深度優(yōu)先遍歷遞歸算法為：（ 1）訪問(wèn)結(jié)點(diǎn) v并標(biāo)記結(jié)點(diǎn) v為已訪問(wèn)；（ 2）查找結(jié)點(diǎn) v的第一個(gè)鄰接結(jié)點(diǎn) w；（ 3）若結(jié)點(diǎn) v的鄰接結(jié)點(diǎn) w存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；（ 4）若結(jié)點(diǎn) w尚未被訪問(wèn)則深度優(yōu)先搜索遞歸訪問(wèn)結(jié)點(diǎn)w；（ 5）查找結(jié)點(diǎn) v的 w鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn) w，轉(zhuǎn)到步驟（ 3）。 2 圖的廣度優(yōu)先遍歷算法 連通圖的廣度優(yōu)先遍歷算法為： （ 1）訪問(wèn)初始結(jié)點(diǎn) v并標(biāo)記結(jié)點(diǎn) v為已訪問(wèn)；（ 2）結(jié)點(diǎn) v入隊(duì)列；（ 3）當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束；（ 4）出隊(duì)列取得隊(duì)頭結(jié)點(diǎn) u；（ 5）查找結(jié)點(diǎn) u的第一個(gè)鄰接結(jié)點(diǎn) w；（ 6）若結(jié)點(diǎn) u的鄰接結(jié)點(diǎn) w不存在，則轉(zhuǎn)到步驟（ 3），否則循環(huán)執(zhí)行， （ ）若結(jié)點(diǎn) w尚未被訪問(wèn)，則訪問(wèn)結(jié)點(diǎn) w，并標(biāo)記結(jié)點(diǎn) w為已訪問(wèn)； （ ）結(jié)點(diǎn) w入隊(duì)列； （ ）查找結(jié)點(diǎn) u的 w鄰接結(jié)點(diǎn)后的下一個(gè)鄰接結(jié)點(diǎn) w，轉(zhuǎn)到步驟（ 6）。3 非連通圖的遍歷 對(duì)于連通圖，從圖的任意一個(gè)結(jié)點(diǎn)開(kāi)始深度或廣度優(yōu)先遍歷，一定可以訪問(wèn)圖中的所有結(jié)點(diǎn)。但對(duì)于非連通圖，從圖的任意一個(gè)結(jié)點(diǎn)開(kāi)始深度或廣度優(yōu)先遍歷，并不能訪問(wèn)圖中的所有結(jié)點(diǎn)。對(duì)于非連通圖，從圖的任意一個(gè)結(jié)點(diǎn)開(kāi)始深度或廣度優(yōu)先遍歷只能訪問(wèn)和初始結(jié)點(diǎn)連通的所有結(jié)點(diǎn)。 圖的深度和廣度優(yōu)先遍歷成員函數(shù)設(shè)計(jì)1 訪問(wèn)結(jié)點(diǎn)2 深度和廣度優(yōu)先遍歷成員函數(shù)設(shè)計(jì)3 測(cè)試程序 最小生成樹(shù) 最小生成樹(shù)的基本概念 一個(gè)有 n個(gè)結(jié)點(diǎn)的連通圖的 生成樹(shù) 是原圖的極小連通子圖，它包含原圖中的所有 n個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。 如果無(wú)向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，我們稱這棵生成樹(shù)為 最小代價(jià)生成樹(shù) ，簡(jiǎn)稱 最小生成樹(shù) 。無(wú)向圖和它的不同的生成樹(shù) 從最小生成樹(shù)的定義可知，構(gòu)造有 n個(gè)結(jié)點(diǎn)的無(wú)向連通帶權(quán)圖的最小生成樹(shù) ,必須滿足以下三條： （ 1）構(gòu)造的最小生成樹(shù)必須包括 n個(gè)結(jié)點(diǎn)； （ 2）構(gòu)造的最小生成樹(shù)中有且只有 n1條邊； （ 3）構(gòu)造的最小生成樹(shù)中不存在回路。 構(gòu)造最小生成樹(shù)的方法有許多種，典型的構(gòu)造方法有兩種，一種稱作 普里姆 （ Prim）算法，另一種稱作 克魯斯卡爾 （ Kruskal）算法。1 普里姆算法思想 假設(shè) G=(V,E)為一個(gè)帶權(quán)圖，其中 V為帶權(quán)圖中結(jié)點(diǎn)的集合， E為帶權(quán)圖中邊的權(quán)值集合。設(shè)置兩個(gè)新的集合 U和 T，其中 U用于存放帶權(quán)圖 G的最小生成樹(shù)的結(jié)點(diǎn)的集合， T用于存放帶權(quán)圖 G的最小生成樹(shù)的權(quán)值的集合。 普里姆算法思想 是：令集合 U的初值為 U={u0}（即假設(shè)構(gòu)造最小生成樹(shù)時(shí)從結(jié)點(diǎn) u0開(kāi)始），集合 T的初值為 T={}。從所有結(jié)點(diǎn) u∈ U和結(jié)點(diǎn) v∈ VU的帶權(quán)邊中選出具有最小權(quán)值的邊 (u,v)，將結(jié)點(diǎn) v加入集合 U中，將邊 (u,v) 加入集合 T中。如此不斷重復(fù)，當(dāng) U=V時(shí)則最小生成樹(shù)構(gòu)造完畢。此時(shí)集合 U中存放著最小生成樹(shù)結(jié)點(diǎn)的集合，集合 T中存放著最小生成樹(shù)邊的權(quán)值集合。普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程2 普里姆函數(shù)設(shè)計(jì) 這里我們令當(dāng)弧頭結(jié)點(diǎn)等于弧尾結(jié)點(diǎn)時(shí)權(quán)值等于 0。 函數(shù)的參數(shù)設(shè)計(jì)： 普里姆函數(shù)應(yīng)有兩個(gè)參數(shù)： 一個(gè)參數(shù)是圖 g，這里圖 g定義為鄰接矩陣存儲(chǔ)結(jié)構(gòu)圖類的對(duì)象； 另一個(gè)參數(shù)是通過(guò)函數(shù)得到的最小生成樹(shù)的結(jié)點(diǎn)數(shù)據(jù)和相應(yīng)結(jié)點(diǎn)的邊的權(quán)值數(shù)據(jù) closeVertex。普里姆算法運(yùn)行時(shí)數(shù)組 lowCost的變化過(guò)程 克魯斯卡爾算法 克魯斯卡爾 算法是：設(shè)無(wú)向連通帶權(quán)圖 G=(V,E)，其中 V為結(jié)點(diǎn)的集合， E為邊的集合。設(shè)帶權(quán)圖 G的最小生成樹(shù) T由結(jié)點(diǎn)集合和邊的集合構(gòu)成，其初值為 T=(V,{})，即初始時(shí)最小生成樹(shù) T只由帶權(quán)圖 G中的結(jié)點(diǎn)集合組成，各結(jié)點(diǎn)之間沒(méi)有一條邊。這樣，最小生成樹(shù) T中的各個(gè)結(jié)點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值遞增的順序考察帶權(quán)圖 G中的邊集合 E中的各條邊。若被考察的邊的兩個(gè)結(jié)點(diǎn)屬于 T的兩個(gè)不同的連通分量，則將此邊加入到最小生成樹(shù) T，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察的邊的兩個(gè)結(jié)點(diǎn)屬于 T的同一個(gè)連通分量，則將此邊舍去。如此下去，當(dāng) T中的連通分量個(gè)數(shù)為 1時(shí)， T中的該連通分量即為帶權(quán)圖 G的一棵最小生成樹(shù)?？唆斔箍査惴?gòu)造最小生成樹(shù)的過(guò)程 最短路徑 最短路徑的基本概念 在一個(gè)圖中，若從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)存在著路徑，定義 路徑長(zhǎng)度 為一條路徑上所經(jīng)過(guò)的邊的數(shù)目。圖中從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可能存在著多條路徑，我們把路徑長(zhǎng)度最短的那條路徑叫做 最短路徑 ，其路徑長(zhǎng)度叫做 最短路徑 長(zhǎng)度或 最短距離 . 在一個(gè)帶權(quán)圖中，若從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)存在著一條路徑，則稱該路徑上所經(jīng)過(guò)邊的權(quán)值之和為該路徑上的 帶權(quán)路徑長(zhǎng)度 。帶權(quán)圖中從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可能存在著多條路徑，我們把帶權(quán)路徑長(zhǎng)度值最小的那條路徑也叫做 最短路徑 ，其帶權(quán)路徑長(zhǎng)度也叫做 最短路徑長(zhǎng)度 或 最短距離 。 從一個(gè)點(diǎn)到其余各結(jié)點(diǎn)的最點(diǎn)路徑 1 狄克斯特拉算法思想 狄克斯特拉算法 是：設(shè)置兩個(gè)結(jié)點(diǎn)的集合 S和 T，集合 S中存放已找到最短路徑的結(jié)點(diǎn)，集合 T中存放當(dāng)前還未找到最短路徑的結(jié)點(diǎn)。初始狀態(tài)時(shí)，集合 S中只包含源點(diǎn)，設(shè)為 v0，然后從集合 T中選擇到源點(diǎn) v0路徑長(zhǎng)度最短的結(jié)點(diǎn) u加入到集合 S中，集合 S中每加入一個(gè)新的結(jié)點(diǎn) u都要修改源點(diǎn) v0到集合 T中剩余結(jié)點(diǎn)的當(dāng)前最短路徑長(zhǎng)度值，集合 T中各結(jié)點(diǎn)的新的當(dāng)前最短路徑長(zhǎng)度值，為原來(lái)的當(dāng)前最短路徑長(zhǎng)度值與從源點(diǎn)過(guò)結(jié)點(diǎn) u到達(dá)該結(jié)點(diǎn)的路徑長(zhǎng)度中的較小者。此過(guò)程不斷重復(fù)，直到集合 T中的結(jié)點(diǎn)全部加入到集合 S 中為止。 下圖為意示例： 每對(duì)結(jié)點(diǎn)之間的最短路徑 弗洛伊德算法是：設(shè)矩陣 cost用來(lái)存放帶權(quán)有向圖 G的權(quán)值，即矩陣元素 cost[i][j]中存放著下標(biāo)為 i的結(jié)點(diǎn)到下標(biāo)為 j的結(jié)點(diǎn)之間的權(quán)值，可以通過(guò)遞推構(gòu)造一個(gè)矩陣序列 A0,A1,A2,……,AN 來(lái)求每對(duì)結(jié)點(diǎn)之間的最短路徑。初始時(shí)有， A0[i][j]=cost[i][j]。當(dāng)已經(jīng)求出Ak,要遞推求解 Ak+1時(shí)，可分兩種情況來(lái)考慮：一種情況是該路徑不經(jīng)過(guò)下標(biāo)為 k+1的結(jié)點(diǎn)，此時(shí)該路徑長(zhǎng)度與從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)下標(biāo)不大于 k的最短路徑長(zhǎng)度相同；另一種情況是該路徑經(jīng)過(guò)下標(biāo)為 k+1的結(jié)點(diǎn)，此時(shí)該路徑可分為兩段，一段是從結(jié)點(diǎn) vi到結(jié)點(diǎn) vk+1的最短路徑，另一段是從結(jié)點(diǎn) vk+1到結(jié)點(diǎn) vj的最短路徑，此時(shí)的最短路徑長(zhǎng)度等于這兩段最短路徑長(zhǎng)度之和。這兩種情況中的路徑長(zhǎng)度較小者，就是要求的從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)下標(biāo)不大于 k+1的最短路徑長(zhǎng)度。弗洛伊德算法的算法思想可用如下遞推公式描述： A0[i][j]=cost[i][j] Ak+1[i][j]=min{Ak[i][j], Ak[i][k+1]+Ak[k+1][j]} （0≤k≤n1） 也就是說(shuō)，初始時(shí)， A0[i][j]=cost[i][j]，然后進(jìn)行遞推，每遞推一次，從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj的最短路徑上就多考慮了一個(gè)經(jīng)過(guò)的中間結(jié)點(diǎn)，這樣，經(jīng)過(guò) n次遞推后得到的 An[i][j]就是考慮了經(jīng)過(guò)圖中所有結(jié)點(diǎn)情況下的從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj的最短路徑長(zhǎng)度。第 9章 排序 排序的基本概念 插入排序 交換排序 歸并排序 基數(shù)排序 各種排序算法的性能比較本章主要知識(shí)點(diǎn)：● 排序的基本概念和衡量排序算法優(yōu)劣的標(biāo)準(zhǔn)，其中衡量標(biāo)準(zhǔn)有算法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性● 直接插入排序，希爾排序● 直接選擇排序，堆排序● 冒泡排序，快速排序● 歸并排序● 基數(shù)排序● 各種排序算法的性能比較 排序的基本概念 排序 是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過(guò)程。 關(guān)鍵 字是要排序的數(shù)據(jù)元素集合中的一個(gè)域，排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的。 關(guān)鍵字 分 主關(guān)鍵字 和 次關(guān)鍵字 兩種。對(duì)要排序的數(shù)據(jù)元素集合來(lái)說(shuō)，如果關(guān)鍵字滿足數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的值也一定不同，這樣的關(guān)鍵字稱為 主關(guān)鍵字 。 不滿足主關(guān)鍵字定義的關(guān)鍵字稱為 次關(guān)鍵字。 學(xué)生成績(jī)表 排序 分 內(nèi)部排序 和 外部排序 兩種。 內(nèi)部排序是把待排數(shù)據(jù)元素全部調(diào)入內(nèi)存中進(jìn)行的排序。如果數(shù)據(jù)元素的數(shù)量太大，需要分批導(dǎo)入內(nèi)存，分批導(dǎo)入內(nèi)存的數(shù)據(jù)元素排好序后再分批導(dǎo)出到磁盤和磁帶外存介質(zhì)上的排序方法稱作 外部排序。 排序算法的比較標(biāo)準(zhǔn)： 1. 空間復(fù)雜度 2. 時(shí)間復(fù)雜度 3. 穩(wěn)定性 插入排序 直插入排序 直接插入排序 的基本思想是：順序地把待排序的數(shù)據(jù)元素按其值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。子集合的數(shù)據(jù)元素個(gè)數(shù)從只有一個(gè)數(shù)據(jù)元素開(kāi)始逐次增大。當(dāng)子集合大小最終和集合大小相同時(shí)排序完畢。 直接插入排序過(guò)程 希爾排序 希爾排序 的基本思想是：把待排序的數(shù)據(jù)元