【正文】 S為已找到的最短路徑的終點集合 For (k=0。 i++) /*最短路徑初始化 */ { dist[i]=cost[0,i]。 ?假設(shè)我們以鄰接矩陣 cost表示所研究的有向圖，cost[i][j]表示有向邊 i, j對應(yīng)權(quán)值，如果兩點之間無相應(yīng)方向的邊，則其值為 ∞ 。 } i++。 克魯斯卡爾算法續(xù) v2=seeks(set,ge[i].tv)。 /* i表示獲取的生成樹中的邊數(shù) ， 初值為 1*/ j=1。 for (i=1。 查找一個頂點所屬的分量函數(shù)如下： int seeks(int set[],int v) { int i=v。當從邊集數(shù)組中按次序選取一條邊時，查找它的兩個頂點所屬的分量，當這兩個分量不相等，則表明所選的這條邊的兩個頂點分屬不同的集合，該邊加入到生成樹中不會形成環(huán)路，應(yīng)作為生成樹的一條邊，同時合并這兩個分量為一個連通分量。如果取到某條邊，發(fā)現(xiàn)它的兩個端點已屬于同一集合時，此邊則應(yīng)當舍去。 ?將每條邊的數(shù)據(jù)輸入之后，按權(quán)值的大小進行了排序，如圖 (b) 所示。 ?這里用 c表示圖的鄰接矩陣， c[i][j]和 c[j][i]是邊 (i,j)的權(quán)。 { closedge[k].lowcost=gn[j, k]。 /*輸出一條邊 closedge [j]. lowcost=0。 /*頂點 1加入 U中 . For( i=1。 圖 普里姆算法例子 8 3 5 ⑤ ④ ① ② ③ 9 14 17 13 12 18 ????????????????????????5181251317141813391738121498C?為了便于在頂點集合 U和 VU之間選擇權(quán)最小的邊，需建立一個數(shù)組 closedge[v], (v∈V U),記錄從 U到 VU之間權(quán)最小的邊 . closedge[v]有兩個字段 : closedge[v].vex: 存放與該邊相關(guān)聯(lián)的在 U中的頂點 , closedge[v].lowcost: 存放該邊的權(quán) . 普里姆算法 : void prim( gn, 1) /*gn: 圖的鄰接矩陣 ， 頂點為 { /* {1,2,… ,n}, 從頂點 1開始 for( i=2, i=n。 算法開始時，首先從 V中任取一個頂點（假定為 V。加入 U 中。開始， 令 U={U。并且將權(quán)最小的生成樹稱為最小生成樹（ Minimum Spanning Tree）。 ?生成樹有如下特點：任意兩個頂點之間有且僅有一條路徑；如果再增加一條邊就會出現(xiàn)回路；如果去掉一條邊此子圖就會變成非連通圖。 } } } 時間復(fù)雜性分析 ?一個有 n個頂點、 e條邊的圖，在廣度優(yōu)先搜索圖的過程中，每個頂點至多進一次隊列，圖的搜索過程實質(zhì)上是通過邊來找頂點的過程，找鄰接點所需時間為 O(e)。 printf(“%d”,padjvex)。 /*初始頂點入隊 */ while(front!=rear) /*隊列不為空 */ 鄰接表表示的圖的 BFS算法 (續(xù) ) { front=front+1。 struct edgenode *p。 (c)w入隊 。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。 ?在廣度優(yōu)先搜索中，若對頂點 V1的訪問先于頂點 V2的訪問，則對 V1鄰接頂點的訪問也先于 V2鄰接頂點的訪問。 } else p=pnext。 if (visited[v]==0) /*若 v未訪問 { stack[++top] =pnext。 visit(adjlist[v0].vexdata)。 非遞歸算法 ?從頂點 Vi出發(fā)進行深度優(yōu)先遍歷的遞歸過程也可以寫成非遞歸的形式，此時需借助一個堆棧保存被訪問過的結(jié)點，以便回溯時查找已被訪問結(jié)點的未被訪問過的鄰接點。 /*從 v未訪問的鄰接點出發(fā)進行 DFS*/ p=p→next 。 } adjlist為鄰接表 ， 從 v0開始 深度優(yōu)先 遍歷的 遞歸 算法 void dfs(adjlist , v0) { visited[v0]=1。 i++) visited[i]=0。 ? 如有未訪問過的相鄰接頂點，則訪問此頂點后，再從該頂點出發(fā)向前進行與前述類似的訪問； ? 如退回一步后，前一頂點也沒有未被訪問過的相鄰接頂點，則再向回退一步進行搜索，重復(fù)上述過程，一直到所有頂點均被訪問過為止。 /*鄰接點序號為 s*/ p→next=g[d] .link。 /*鄰接點序號為 d*/ p→next=g[s] .link。s,amp。 } for(i=1。i++) { printf(“\n請輸入第 %d個頂點信息： ” ,i)。n,amp。 產(chǎn)生無向圖的鄰接表算法 void creategraph (adjlist g) { int e,i,s,d,n。 Typedef struct vexnode /*表頭結(jié)點 */ { char vexdata。 鄰接表存儲結(jié)構(gòu)定義 define maxvex 30 typedef struct edgenode /*邊表結(jié)點 */ { int adjvex 。 ?在 無向圖 的鄰接表中，各頂點對應(yīng)的單鏈表的結(jié)點數(shù)（不算表頭結(jié)點）就等于該頂點的度數(shù)。 ?在鄰接表結(jié)構(gòu)中，對圖中每個頂點建立一個單鏈表，第 i個單鏈表中的結(jié)點表示與結(jié)點 Vi相關(guān)連的邊；對于有向圖則表示以該頂點為起點的一條邊的終點。 v2!=0)。 /*輸入邊 */ adjarray[v1][v2]=1。 j++) adjarry [i][j]=0。 /*輸入頂點數(shù) */ if (num0) { for (i=1。 結(jié)點 Vi的出度 OD(Vi), 是鄰接矩陣中 ,第 i行 1的個數(shù) . 結(jié)點 Vi的入度 ID(Vi), 是鄰接矩陣中 ,第 i列 1的個數(shù) . 對于 有權(quán)圖 (網(wǎng)） 例： 鄰接矩陣用二維數(shù)組即可存儲，定義如下： int adjmatrix ARRAY[n][n]。所謂兩頂點的相鄰關(guān)系即它們之間有邊相連。=V， E39。 圖 非連通圖 G ④ ① ③ ⑦ ⑧ ② ⑤ ?強連通圖和強連通分量：在有向圖 G中，如果從頂點 Vi到頂點 Vj和從頂點 Vj到頂點 Vi之間都有路徑，則稱這兩個頂點是強連通的。 ?路徑長度：對于無權(quán)的圖，路徑長度指的是沿此路徑上邊的數(shù)目；對于有權(quán)圖，一般是取沿路徑各邊的權(quán)之和作為此路徑的長度。 ?入度、出度：對于有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數(shù)目；出度是以該頂點為起點的出邊數(shù)目，該頂點的度等于其入度和出度之和。邊上帶權(quán)的圖稱為帶權(quán)圖，也稱為網(wǎng)絡(luò)(Network)。 圖 有向圖與無向圖 ?無向圖 G1 ④ ① ② ③ ⑤ ④ ① ② ③ ?有向圖 G2 ?完全圖：在一個有 n個頂點的無向圖中，若每個頂點到其它（ n1）個頂點都連有一條邊，這種圖稱為完全圖。 ?有向圖：對于一個圖 G，若邊集合 E（ G）為有向邊的集合，則稱該圖為有向圖。 ?權(quán)和網(wǎng)絡(luò)：有些圖， 對應(yīng)每條邊有一相應(yīng)的數(shù)值，這個數(shù)值叫做該邊的權(quán) (Weight)。 圖 子圖 ④ ① ② ③ ⑤ 4 ① ② ③ ⑤ ?頂點的度：圖中與每個頂點相連的邊數(shù)，叫該頂點的度 (Degree)，記作 TD（ V）。 若其中間頂點不重復(fù)，則稱 簡單路徑 ；若第 1個頂點和最后一個頂點相同，則稱為 回路 。 ?連通分量：非連通圖的每一個極大連通子圖叫連通分量 (Connected Component)。 ?生成樹：有 n個頂點， n1條邊的樹，且 V39。鄰接矩陣表示法 ? 鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。所以，只存儲其上三角陣元素即可 . 2. 對無向圖 , 結(jié)點 Vi的度 , 是鄰接矩陣中 ,第 i行 1的個數(shù) . 對 有向圖 , 鄰接矩陣一般是不對稱的， A[i， j]不一定等于 A[j， i]。num)。 j=num。v2)。amp。 } 2. 鄰接表 ?鄰接表是圖的一種鏈接存儲結(jié)構(gòu)。 有兩種結(jié)點： 1. 表頭結(jié)點： 每個鏈表設(shè)一表頭結(jié)點 Vexdata firstarc Vexdata：結(jié)點信息 Firstarc: 第一條邊 2. 邊表結(jié)點 ： vertex：存放與頂點 Vi相鄰接的頂點 nextarc：指向依附于頂點 Vi的下一條邊所對 應(yīng)的結(jié)點 Info： 有權(quán)圖 （ 網(wǎng)絡(luò)） 中邊的權(quán)值 例：無向圖，有向圖