【正文】 圖 ， 否則需要多次調(diào)用DFS(G,v)。v++) if(!visited[v]) DFS(G,v)。 adbg無 向 圖 G6cefhiadbgcefhi1234567891 01 31 41 11 21 51 6圖 G6的 深 度 優(yōu) 先 遍 歷 過 程 圖的遍歷 2．圖的深度優(yōu)先搜索遍歷的算法實現(xiàn) 圖的深度優(yōu)先遍歷（鄰接表實現(xiàn)）的算法描述如下。 /*圖的頂點數(shù)目與邊的數(shù)目 */ }AdjMultiGraph。 /*訪問標(biāo)志和邊的兩個頂點位置 */ InfoPtr *info。 int vexnum,arum。 有 向 圖 G1 0 1 0 3 ^abcd0數(shù) 組 編 號 2 0 2 1 ^ ^1233 2 ^ ^a db c^ 1 2 ^ ^ 圖的存儲結(jié)構(gòu) 有向圖的十字鏈表存儲結(jié)構(gòu)描述如下： define MaxSize 50 /*最大頂點個數(shù) */ typedef struct ArcNode /*弧結(jié)點的類型定義 */ { int headvex,tailvex。i++) /*將頂點存儲在表頭結(jié)點中 */ { scanf(%s,Gvertex[i].data)。因此如果要求某個頂點的入度 ， 則需要對整個鄰接表進(jìn)行遍歷 。 圖的存儲結(jié)構(gòu) typedef struct /*圖的類型定義 */ { AdjList vertex。 1 3 2 ^ 0 1 ^ 2 ^abcd0123表 頭 結(jié) 點 邊 表 結(jié) 點數(shù) 組 編 號 1 2 0 1 0abcd0123表 頭 結(jié) 點 邊 表 結(jié) 點數(shù) 組 編 號 0 2 2^ 3 ^^ 3 ^^^表 頭 結(jié) 點 邊 表 結(jié) 點 1 6 5 1 4 / \ 2 3abcd0數(shù) 組 編 號 2 8 5 1 2 / \ 4 4 / \12345ef 0 9 / \ 3 7 / \ 圖的存儲結(jié)構(gòu) 圖的鄰接表存儲結(jié)構(gòu)描述如下： define MaxSize 50 /*最大頂點個數(shù) */ typedef enum{DG,DN,UG,UN}GraphKind。采用鄰接表表示圖一般需要兩個表結(jié)構(gòu)：邊表和表頭結(jié)點表。 /*鄰接矩陣，存儲邊或弧的信息 */ int vexnum,arum。它們的鄰接矩陣表示如圖。在圖 G中刪除弧 v,w。G,v)：圖的頂點刪除操作。在圖 G中查找 v的第一個鄰接頂點，并將其返回。 （ 3） DestroyGraph(amp。一個網(wǎng)如圖 所示。一棵具有 n個頂點的生成樹僅有 n1條邊，如果少于 n1條邊，則該圖是非連通的。對于無向圖，邊數(shù) e的取值范圍為 0~n(n1)/2。如果對于圖中任意兩個頂點 vi、 vj∈ V， vi和 vj都是連通的，則稱 G是連通圖（ connected graph）。第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)（ cycle）。 圖的定義與相關(guān)概念 2．頂點的度 對于無向圖，頂點 v的度是指與 v相關(guān)聯(lián)的邊的數(shù)目，記作 TD(v)。 圖的定義與相關(guān)概念 1．鄰接點 對于無向圖 G=(V,E)，若邊 (vi,vj)∈ E，則稱 vi和 vj互為鄰接點（ adjacent），即 vi和 vj相鄰接。 若 x,y∈ E，則 x,y表示從頂點 x到頂點 y存在一條?。?Arc）， x稱為弧尾（ tail）或起始點（ initial node）， y稱為弧頭（ head）或終端點（ terminal node）。第 10章 圖 圖 (graph)是一種比線性表 、 樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 。這樣的圖被稱為有向圖（ digraph）。邊 (vi,vj)依附于頂點 vi和 vj，或者說 (vi,vj)與頂點 vi、 vj相關(guān)聯(lián)。對于有向圖，以頂點 v為弧頭的數(shù)目稱為頂點 v的入度 (indegree)，記作ID(v)。序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑。無向圖中的極大連通子圖稱為連通分量。將具有 n(n1)/2條邊的無向圖稱為完全圖（ pleted graph）或無向完全圖。多于 n1條邊，則一定有環(huán)的出現(xiàn)。 a db ce51 271 0864 圖的定義與相關(guān)概念 圖的抽象數(shù)據(jù)類型 1．?dāng)?shù)據(jù)對象集合 圖的數(shù)據(jù)對象為圖的各個頂點和邊的集合。T)：銷毀圖的操作。如果在 G中沒有鄰接頂點，則返回 1。將圖 G中的頂點 v及相關(guān)聯(lián)的弧刪除。對于無向圖，還要刪除弧 w,v。 帶權(quán)圖的鄰接矩陣表示如圖 。 /*頂點數(shù)和邊（?。┑臄?shù)目 */ GraphKind kind。 邊表：在鄰接表中，對圖中的每個頂點都建立一個單鏈表，第 i個單鏈表中的結(jié)點表示依附于頂點 vi的邊（對有向圖來說是以頂點 vi為尾的弧），這種鏈表稱為邊表，其中結(jié)點稱為弧結(jié)點，弧結(jié)點由 3個域組成：鄰接點域（ adjvex）、數(shù)據(jù)域（ info）和指針域（ nextarc）。 /*圖的類型：有向圖、有向網(wǎng)、無向圖和無向網(wǎng) */ typedef struct ArcNode /*邊結(jié)點的類型定義 */ { int adjvex。 int vexnum,arum。圖 G1的逆鄰接鏈表如圖 。 Gvertex[i].firstarc=NULL。 /*弧的頭頂點和尾頂點位置 */ InfoPtr *info。 /*圖的頂點數(shù)目與弧的數(shù)目 */ }OLGraph。 /*與邊相關(guān)的信息 */ struct *ilink,*jlink。 圖的遍歷 與樹的遍歷類似，我們希望從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。 int visited[MaxSize]。 /*對未訪問的頂點 v進(jìn)行深度優(yōu)先搜索遍歷 */ printf(\n)。 在遍歷圖時 ， 對圖中的每個頂點至多調(diào)用一次 DFS(G,v)函數(shù) ， 因為一旦某個頂點被標(biāo)志為已被訪問 ， 就不再從它出發(fā)進(jìn)行搜索 。 /*訪問標(biāo)志設(shè)置為已訪問 */ Visit([v].data)。 /*v1為頂點 v在圖 G中的序號*/ p=[v1].firstarc。 /*w1為頂點 w在圖 G中的序號 */ for(next=[v1].firstarc。若此時圖中還有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復(fù)上述過程，直至圖中的所有頂點都被訪問到為止。依次類推，直到圖中的所有頂點都已被訪問過。v++) /*初始化標(biāo)志位 */ visited[v]=0。 /*隊頭元素出隊賦值給 v*/ p=[v].firstarc。對于非連通圖，則需從多個頂點出發(fā)進(jìn)行搜索，而每一次從一個新的起始點出發(fā)進(jìn)行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。 圖 G6的深度優(yōu)先生成樹和廣度優(yōu)先生成樹 。這個問題就是構(gòu)造連通網(wǎng)的最小代價生成樹（ minimum cost spanning tree） (簡稱為最小生成樹 )問題。另外 T中一定存在一條邊(u’,v’)的權(quán)值大于或等于 (u,v)的權(quán)值，如果刪除邊 (u’,v’)，則得到一棵代價小于或等于 T的生成樹 T’。 這時，邊集合 TE一定有 n1條邊， T={V,TE}就是連通網(wǎng) N的最小生成樹。用公式描述為： closeedge[v].lowcost=Min({cost(u,v)|u∈ U}) 表 普里姆算法各個參數(shù)的變化 a d j v e xl o w c o s ta d j v e xl o w c o s ta d j v e xl o w c o s ta d j v e xl o w c o s ta d j v e xl o w c o s tic l o s e e d g e [ i ]0 1 2 43 UV Uk ( u0, v0)00000a6a1a5c60{ a } { b , c , d , e , f }2 ( a , c )c5a5c6{ a , c , f }{ a , c }{ a , c , d , f }{ a , b , c , d , f }0c6000000 0 00{ b , d , e , f }{ b , d , e }{ b , e }{ e }531( c , f )( d , f )( b , c )5a d j v e xl o w c o s t0c4000c5f2c5b3{ }4( b , e )0{ a , b , c , d , e , f } 圖的連通性問題 【 例 10_4】 創(chuàng)建一個如圖 N，然后利用普里姆算法求無向網(wǎng)的最小生成樹。 然后對 closedge進(jìn)行初始化，即把初始頂點賦給 closedge的 adjvex域，最小代價邊賦給 lowcost域，并將第一個頂點加入 U集。代碼如下。j。 b de fc( a ) 初 始 狀 態(tài)ab de fc( b ) 邊 a c 加 入 集 合 E 中a1b de fc2( c ) 邊 d f 加 入 集 合 E 中a1b de fc2( d ) 邊 b c 加 入 集 合 E 中a1b de fc42( e ) 邊 c f 加 入 集 合 E 中a1b de fc3425( f ) 邊 b c 加 入 集 合 E 中a13 有向無環(huán)圖 AOV網(wǎng)與拓?fù)渑判? 1．什么是 AOV網(wǎng) 幾乎所有的工程都可分為若干個稱為活動的子工程，而這些子工程之間，通常受一些條件的制約，如某些子工程的開始必須在另一些子工程完成之后才能進(jìn)行。 圖中的弧表示課程之間的制約關(guān)系 。通常，可用 AOE網(wǎng)估算工程的完成時間。 在 AOE網(wǎng)中，有些活動是可以并行執(zhí)行的，關(guān)鍵路徑其實就是完成工程的最短時間所經(jīng)過的路徑。 （ 3）活動 ai的最早開始時間 e(i)：如果弧 vk,vj表示活動 ai，當(dāng)事件 vk發(fā)生之后，活動 ai才開始。否則，從源點 v0開始，求出各個頂點的最早發(fā)生時間 ve(i)。 （ 3）由各頂點的最早發(fā)生時間 ve(i)和最晚發(fā)生時間 vl(i)，求出每個活動 ai的最早開始時間 e(i)和最晚開始時間 l(i)。 有向無環(huán)圖 （ 4） 活動 ai的最晚開始時間 l(i)：在不推遲整個工程完成時間的基礎(chǔ)上 ， 活動 ai最遲必須開始的時間 。 有向無環(huán)圖 （ 1）事件 vi的最早發(fā)生時間 ve(i)：從源點到頂點 vi的最長路徑長度，稱為事件 vi的最早發(fā)生時間，記作 ve(i)。 進(jìn)入頂點的有向弧表示的活動已經(jīng)完成 ， 從頂點出發(fā)的有向弧表示的活動可以開始 。 按照以上方法，可得到圖 (當(dāng)然還可構(gòu)造其他的拓?fù)湫蛄?)為： (C1,C6,C10,C7,C2,C3,C4,C5,C8,C9)和 (C2,C1,C3,C4,C5,C9,C10,C6,C7,C8) 圖 。 在 AOV網(wǎng)中，若從頂點 vi到頂點 vj之間存在一條有向路徑，則頂點 vi是頂點 vj的前驅(qū)，頂點 vj為頂點 vi的后繼。 closedge[j].lowcost=[k][j].adj。i。 for(j=0。數(shù)組closedge有兩個域： a