【正文】 dist[u] + Edge[u][w] dist[w] ) { //頂點(diǎn) w未加入 S, 且繞過 u可以縮短路徑 dist[w] = dist[u] + Edge[u][w]。 w++ ) //修改 if ( !S[w] amp。 min = dist[j]。 j n。 i n1。 else path[i] = 1。 //dist數(shù)組初始化 S[i] = 0。本算法建立起 //一個(gè)數(shù)組 : dist[j], 0? jn, 是當(dāng)前求到的從頂 //點(diǎn) v 到頂點(diǎn) j 的最短路徑長度 , 同時(shí)用數(shù)組 //path[j], 0? jn, 存放求到的最短路徑 。 //最短路徑頂點(diǎn)集 public: void ShortestPath ( int, int )。 //圖最大頂點(diǎn)個(gè)數(shù) class Graph { //圖的類定義 private: float Edge[NumVertices][NumVertices]。 S ← S U { k }。 ? 每次求得一條最短路徑后 , 其終點(diǎn) vk 加入集合S，然后 對所有的 vi ?VS，修改其 dist[i]值 。 ? 舉例說明 Dijkstra逐步求解的過程 1 0 4 3 2 10 100 30 50 20 60 10 源點(diǎn) 終點(diǎn) 最短路徑 路徑長度 v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2) ?,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 ? 引入輔助數(shù)組 dist。 ? 問題解法 ? 邊上權(quán)值非負(fù)情形的單源最短路徑問題 — Dijkstra算法 ? (僅講此算法 ) ? 邊上權(quán)值為任意值的單源最短路徑問題 — Bellman和 Ford算法 ? (不講 ) ? 所有頂點(diǎn)之間的最短路徑 — Floyd算法 ? (不講 ) 邊上權(quán)值非負(fù)情形的單源最短路徑問題 ? 問題的提法： 給定一個(gè)帶權(quán)有向圖 D與源點(diǎn) v，求從 v 到 D中其它頂點(diǎn)的最短路徑。 Edge[v][j] lowcost[j] ) { lowcost[j] = Edge[v][j]。 //該邊加入生成樹標(biāo)記 for ( j = 1。 = v。amp。 int v = 0。 //加到生成樹頂點(diǎn)集合 MSTEdgeNode e。 i NumVertices。T ) { int NumVertices = 。 ? 取 lowcost[i] = min{ lowcost[i], Edge[v][i] }， 即用 生成樹頂點(diǎn)集合外各頂點(diǎn) i 到剛加入該集合的新頂點(diǎn) v 的距離 Edge[v][i] 與 原來它們到生成樹頂點(diǎn)集合中頂點(diǎn)的最短距離 lowcost[i] 做比較 , 取距離近的作為這些集合外頂點(diǎn)到生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)的最短距離。 lowcost[i]最小 的邊 , 用 v 標(biāo)記它。 ? 采用鄰接矩陣作為圖的存儲(chǔ)表示。 //該邊存入最小生成樹 count++。 //從堆中退出一條邊 u = ( )。 //插入堆 = Edge[u][v]。 u++ ) for ( int v = u +1。 int NumVertices = 。 item )。 class MinSpanTree { protected: MSTEdgeNode * edgevalue。 class MSTEdgeNode { //生成樹邊結(jié)點(diǎn)類 friend class MinSpanTree。 ? 算法的框架 利用最小堆 (MinHeap)和并查集 (DisjointSets)來實(shí)現(xiàn) 克魯斯卡爾算法 。 克魯斯卡爾 (Kruskal) 算法 ? 克魯斯卡爾算法的基本思想： 設(shè)有一個(gè)有 n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò) N = { V, E }, 最初先構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn) , 沒有邊的非連通圖 T = { V, ? }, 圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。 ? 其它頂點(diǎn) u 是 關(guān)節(jié)點(diǎn) 的充要條件是 它至少有一個(gè)子女 w, 從 w 出發(fā) , 不能通過 w、 w 的子孫及一條回邊所組成的路徑到達(dá) u 的祖先 。 ? 一個(gè)連通圖 G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量。 //遞歸建立 w 的以 p 為根的 子樹 } //鄰接頂點(diǎn) w 處理完 w = GetNextNeighbor ( v, w )。 //第一個(gè)未訪問子女應(yīng)是 v 的左子女 while ( w ) { //鄰接頂點(diǎn) w 存在 if ( ! visited [w] ) { // w未訪問過 , 將成為 v 的子女 if ( FirstChild ) { p = ( RT,GetValue(w) )。T, TreeNode Type*RT, int v, int visited [ ] ) { TreeNodeType * p。 i++ ) //遍歷所有頂點(diǎn) if ( !visited[i] ) { //頂點(diǎn) i 未訪問過 if ( ( ) ) //原為空森林 ,建根 subT = rt = ( GetValue(i) )。 i n。 } templateclass Type void Graph Type :: DFS_Forest ( Tree Type amp。 i++ ) if ( !visited[i] ) { //檢測頂點(diǎn)是否訪問過 DFS ( i, visited )。 i NumVertices。 ? 在算法中 , 需要對圖的每一個(gè)頂點(diǎn)進(jìn)行檢測：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量。 } w = GetNextNeighbor (v, w)。 int w = GetFirstNeighbor (v)。 Queueint q。 i++ ) visited[i] = 0。 ? 為避免重復(fù)訪問 , 需要一個(gè)輔助數(shù)組 visited [ ]，給被訪問過的頂點(diǎn)加標(biāo)記。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)， … 如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。 //頂點(diǎn) v 作訪問標(biāo)記 int w = GetFirstNeighbor (v)。 //訪問數(shù)組 visited 初始化 DFS (0, visited )。 圖的深度優(yōu)先搜索算法 templateclass Type void Graph Type :: DFS ( ) { int * visited = new int [NumVertices]。接著 , 退回一步 , 退到前一次剛訪問過的頂點(diǎn) , 看是否還有其它沒有被訪問的鄰接頂點(diǎn)。 ? 輔助數(shù)組 visited [ ] 的初始狀態(tài)為 0, 在圖的遍歷過程中 , 一旦某一個(gè)頂點(diǎn) i 被訪問 , 就立即讓 visited [i] 為 1, 防止它被多次訪問。需要時(shí)還可有權(quán)值域 cost。用有向圖的鄰接多重表 (十字鏈表 )可把兩個(gè)表結(jié)合起來表示。在鄰接多重表中 , 所有依附同一個(gè)頂點(diǎn)的邊都鏈接在同一個(gè)單鏈表中。 ? 無向圖的情形 ? 邊結(jié)點(diǎn)的結(jié)構(gòu) mark vertex1 vertex2 path1 path2 其中 , mark 是記錄是否處理過的標(biāo)記 。 else p = plink。 //沒有查到下一個(gè)鄰接頂點(diǎn) } template Class Type float Graph Type :: GetWeight ( int v1, int v2) { //取兩端點(diǎn)為 v1 和 v2 的邊上的權(quán)值 if ( v1 != 1 amp。amp。 if ( p != NULL ) return pdest。 i NumVertices。 delete p。 //插入邊 } } template class Type Graph Type :: ~Graph ( ) { for ( int i = 0。 i++) { //逐條邊輸入 cin tail head weight。 InsertVertex ( name )。 cin n。 } 鄰接表的構(gòu)造函數(shù)和析構(gòu)函數(shù) template class Type Graph Type :: Graph ( int sz = DefaultSize ) : NumVertices (0), MaxVertices (sz), NumEdges (0){ int n, e, k, j。 void RemoveEdge ( int v1, int v2 )。 } int NumberOfEdges ( ) { return NumEdges。 } NameType GetValue ( int i ) { return i = 0 amp。 public: Graph ( int sz )。 //頂點(diǎn)表 int NumVertices。 } } template class Type struct Vertex { //頂點(diǎn)friend class Graph Type。 //目標(biāo)頂點(diǎn)下標(biāo) float cost。 ? 設(shè)圖中有 n 個(gè)頂點(diǎn)， e 條邊，則 用鄰接表表示無向圖時(shí) ，需要 n 個(gè)頂點(diǎn)結(jié)點(diǎn)， 2e 個(gè)邊結(jié)點(diǎn)；用 鄰接表表示有向圖時(shí) ，若不考慮逆鄰接表，只需 n 個(gè)頂點(diǎn)結(jié)點(diǎn)， e 個(gè)邊結(jié)點(diǎn)。 } 鄰接表 (Adjacency List) ? 無向圖的鄰接表 同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊 (邊結(jié)點(diǎn) ), 結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo) dest 和指針 link。 col++ ) if ( Edge[v][col] 0 amp。 if ( v != 1 amp。amp。 else return 0。 CurrentEdges = 0。 i sz。 void InsertEdge ( int v1, int v2, float weight )。 } DistType GetWeight ( int v1, int v2 )。 } int NumberOfEdges ( ) { return CurrentEdges。 } public: Graph ( int sz = MaxEdges )。 int FindVertex (SeqList Type amp。 const int MaxVertices = 10。 ? 有向圖的鄰接矩陣可能是不對稱的。 int GetFirstNeighbor ( int v )。 void RemoveVertex ( int v )。 圖的抽象數(shù)據(jù)類型 class Graph { public: Graph ( )。非連通圖的極大連通子圖叫做連通分量。