【正文】 visited[v0]=1。 in。 i++) visited[i]=0。 鄰接表表示的圖的 DFS算法 adjlist為鄰接表 ， 從 v0開始 深度優(yōu)先 遍歷 void DFStraverse(adjlist) { for(i=0。 ? 如有未訪問過的相鄰接頂點(diǎn)，則訪問此頂點(diǎn)后，再從該頂點(diǎn)出發(fā)向前進(jìn)行與前述類似的訪問； ? 如退回一步后，前一頂點(diǎn)也沒有未被訪問過的相鄰接頂點(diǎn)，則再向回退一步進(jìn)行搜索，重復(fù)上述過程，一直到所有頂點(diǎn)均被訪問過為止。 /*將新結(jié)點(diǎn)插入頂點(diǎn) Vd邊表的頭部 */ } } 返回 對有向圖 , 也可采用十字鏈表法 4. 鄰接多重表存儲法 用于無向圖 圖的遍歷 ? 1。 /*鄰接點(diǎn)序號為 s*/ p→next=g[d] .link。 /*將新結(jié)點(diǎn)插入頂點(diǎn) Vs邊表的頭部 */ p=(struct edgenode *)malloc(sizeof(edgenode))。 /*鄰接點(diǎn)序號為 d*/ p→next=g[s] .link。 p=(struct edgenode *)malloc(sizeof(edgenode))。s,amp。i++) 產(chǎn)生無向圖的鄰接表算法 (續(xù) ) { printf(“\n請輸入第 %d條邊起點(diǎn)序號 ， 終點(diǎn)序號： ” ,i)。 } for(i=1。g[i].data)。i++) { printf(“\n請輸入第 %d個(gè)頂點(diǎn)信息： ” ,i)。 for(i=1。n,amp。 printf(“請輸入結(jié)點(diǎn)數(shù) (n)和邊數(shù) (e):\n”)。 產(chǎn)生無向圖的鄰接表算法 void creategraph (adjlist g) { int e,i,s,d,n。 }vexnode。 Typedef struct vexnode /*表頭結(jié)點(diǎn) */ { char vexdata。 /*邊的信息 * struct edgenode *nextarc 。 鄰接表存儲結(jié)構(gòu)定義 define maxvex 30 typedef struct edgenode /*邊表結(jié)點(diǎn) */ { int adjvex 。 ?在 有向圖 鄰接表中，單鏈表的結(jié)點(diǎn)數(shù)就等于相應(yīng)頂點(diǎn)的出度數(shù)。 ?在 無向圖 的鄰接表中，各頂點(diǎn)對應(yīng)的單鏈表的結(jié)點(diǎn)數(shù)（不算表頭結(jié)點(diǎn)）就等于該頂點(diǎn)的度數(shù)。因?yàn)樵卩徑颖淼拿總€(gè)單鏈表中，各結(jié)點(diǎn)的順序是任意的。 ?在鄰接表結(jié)構(gòu)中，對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第 i個(gè)單鏈表中的結(jié)點(diǎn)表示與結(jié)點(diǎn) Vi相關(guān)連的邊；對于有向圖則表示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。 retrun （ num） 。 v2!=0)。 } while(v1!=0 amp。 /*輸入邊 */ adjarray[v1][v2]=1。v1,amp。 j++) adjarry [i][j]=0。 i++) for (j=1。 /*輸入頂點(diǎn)數(shù) */ if (num0) { for (i=1。 scanf (“%d”,amp。 結(jié)點(diǎn) Vi的出度 OD(Vi), 是鄰接矩陣中 ,第 i行 1的個(gè)數(shù) . 結(jié)點(diǎn) Vi的入度 ID(Vi), 是鄰接矩陣中 ,第 i列 1的個(gè)數(shù) . 對于 有權(quán)圖 (網(wǎng)） 例： 鄰接矩陣用二維數(shù)組即可存儲，定義如下： int adjmatrix ARRAY[n][n]。 對無權(quán)圖， ??? ???反之邊邊，對有向圖若存在對無向圖若存在0,),(1],[ jiji VVVVjiA圖 無向圖的鄰接矩陣 ○ A ○ B ○C ○ D DCBAA?????????????0111101111011110A B C D 圖 有向圖的鄰接矩陣 ○ A ○ B ○ C A B C CBAB???????????010100110可以看出 : 1. 無向圖的鄰接矩陣是對稱的， 即若 A[i， j]=1，必有 A[j， i]=1。所謂兩頂點(diǎn)的相鄰關(guān)系即它們之間有邊相連。 圖 圖 G2的強(qiáng)連通分量 ④ ① ③ ② 返回 圖的存儲結(jié)構(gòu) 1。=V， E39。非強(qiáng)連通圖的每一個(gè)極大強(qiáng)連通子圖叫做強(qiáng)連通分量。 圖 非連通圖 G ④ ① ③ ⑦ ⑧ ② ⑤ ?強(qiáng)連通圖和強(qiáng)連通分量：在有向圖 G中，如果從頂點(diǎn) Vi到頂點(diǎn) Vj和從頂點(diǎn) Vj到頂點(diǎn) Vi之間都有路徑，則稱這兩個(gè)頂點(diǎn)是強(qiáng)連通的。如果圖中任意一對頂點(diǎn)都是連通的，則稱此圖是連通圖 (Connected graph)。 ?路徑長度：對于無權(quán)的圖，路徑長度指的是沿此路徑上邊的數(shù)目；對于有權(quán)圖，一般是取沿路徑各邊的權(quán)之和作為此路徑的長度。 ?路徑（回路）：若從某頂點(diǎn) Vp出發(fā)，沿一些邊經(jīng)過頂點(diǎn) V1,V2,…,V m到達(dá)， Vq，則稱頂點(diǎn)序列(Vp, V1,V2,…,V m, Vq)為從 Vp到 Vq的 路徑 (Path)。 ?入度、出度：對于有向圖，頂點(diǎn)的度分為入度和出度，入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目；出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目，該頂點(diǎn)的度等于其入度和出度之和。 ?例如圖 G1的一些子圖。邊上帶權(quán)的圖稱為帶權(quán)圖，也稱為網(wǎng)絡(luò)(Network)。 ④ ① ② ③ ?左圖所示就是 n=4的完全圖，它一共有六條邊。 圖 有向圖與無向圖 ?無向圖 G1 ④ ① ② ③ ⑤ ④ ① ② ③ ?有向圖 G2 ?完全圖：在一個(gè)有 n個(gè)頂點(diǎn)的無向圖中，若每個(gè)頂點(diǎn)到其它（ n1）個(gè)頂點(diǎn)都連有一條邊，這種圖稱為完全圖。數(shù)據(jù)結(jié)構(gòu) 第 7章 圖 第 7章 圖 ?知 識 點(diǎn) 圖的邏輯結(jié)構(gòu)特征及圖的基本術(shù)語 鄰接矩陣和鄰接表兩種圖的存儲結(jié)構(gòu)的特點(diǎn)及適用范圍 深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法的特點(diǎn)和執(zhí)行過程 生成樹和最小生成樹的概念及構(gòu)造最小生成樹的 prim和 kruskal算法 最短路徑的含義及求最短路徑的算法 拓?fù)渑判虻幕舅枷牒筒襟E 關(guān)鍵路徑法及其在管理科學(xué)中的作用 ?難 點(diǎn) 圖的遍歷、最小生成樹、最短路徑、拓樸排序算法的理解 關(guān)鍵路徑法求關(guān)鍵活動和關(guān)鍵路徑的方法 ?要 求 熟練掌握以下內(nèi)容： 圖的存儲結(jié)構(gòu) 圖的遍歷算法 了解以下內(nèi)容： 圖的最小生成樹和求最小生成樹算法的基本思想 帶權(quán)有向圖的最短路徑問題 利用 AOV網(wǎng)絡(luò)的拓樸排序問題 利用 AOE網(wǎng)絡(luò)的關(guān)鍵路徑法 圖的定義和基本術(shù)語 ?圖是一個(gè)二元組 G=（ V， E） 其中 V={x | x?data object} 點(diǎn)的集合 E={x,y | p(x,y) ? x, y ? V} 邊的集合 P(x,y)表示從 x到 y的一條邊 ?無向圖：對于一個(gè)圖 G，若邊集合 E（ G）為無向邊的集合，則稱該圖為無向圖。 ?有向圖：對于一個(gè)圖 G，若邊集合 E（ G）為有向邊的集合，則稱該圖為有向圖。完全圖中共有 n(n1)/2條邊，（ Complete graph，也稱完備圖）。 ?權(quán)和網(wǎng)絡(luò)：有些圖， 對應(yīng)每條邊有一相應(yīng)的數(shù)值，這個(gè)數(shù)值叫做該邊的權(quán) (Weight)。 ?子圖：設(shè)有兩個(gè)圖 G =(V,E)和 G’=(V’,E’)，若V(G’)?V(G)， E(G’)? E(G)，則稱 G’是 G的子圖 (Subgraph)。 圖 子圖 ④ ① ② ③ ⑤ 4 ① ② ③ ⑤ ?頂點(diǎn)的度：圖中與每個(gè)頂點(diǎn)相連的邊數(shù)，叫該頂點(diǎn)的度 (Degree)，記作 TD（ V）。分別記作 ID（ V）， OD（ V）。 若其中間頂點(diǎn)不重復(fù)，則稱 簡單路徑 ；若第 1個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則稱為 回路 。 ?連通、連通圖：在無向圖中，如果從頂點(diǎn)Vi到頂點(diǎn) Vj之間有路徑，則稱這兩個(gè)頂點(diǎn)是連通的。 ?連通分量：非連通圖的每一個(gè)極大連通子圖叫連通分量 (Connected Component)。如果圖中任何一對頂點(diǎn)都是強(qiáng)連通的，則此圖叫做強(qiáng)連通圖。 ?生成樹：有 n個(gè)頂點(diǎn)， n1條邊的樹，且 V39。?E。鄰接矩陣表示法 ? 鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。 ? 若圖有 n個(gè)結(jié)點(diǎn)數(shù)，鄰接矩陣是一個(gè)（ n n）階方陣。所以，只存儲其上三角陣元素即可 . 2. 對無向圖 , 結(jié)點(diǎn) Vi的度 , 是鄰接矩陣中 ,第 i行 1的個(gè)數(shù) . 對 有向圖 , 鄰接矩陣一般是不對稱的， A[i， j]不一定等于 A[j， i]。 產(chǎn)生無向圖鄰接矩陣算法 void creatgraph (int adjarray[ ][ ]) { int i, j, v1, v2, num。num)。 i=num。 j=num。 /*矩陣初始化 */ do { scanf (“%d,%d”,amp。v2)。 adjarray[v2][v1]=1。amp。 } else num=0。 } 2. 鄰接表 ?鄰接表是圖的一種鏈接存儲結(jié)構(gòu)。 ?一個(gè)圖的鄰接矩陣表示是唯一的，但其鄰接表表示是不唯一的。 有