【正文】 從 v 到 w弧， 謂詞 P(v,w) 定義了弧 v,w的意義或信息。 PutVex(amp。若 w 是 v 的最后一個鄰接點(diǎn)，則 // 返回“空”。G, v, w)。 //廣度優(yōu)先遍歷圖 G，并對每個頂點(diǎn)調(diào) //用函數(shù) Visit一次且僅一次。 頂點(diǎn)表： 1 10 1 1 0 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等。對帶權(quán)圖 ,則為 權(quán)值 類型。 // 圖的種類標(biāo)志 } MGraph。++i)scanf(amp。++k){//構(gòu)造鄰接矩陣 Scanf(amp。 //若弧含有相關(guān)信息 ,則輸入 [j][i]=[i][j]。 adjvex nextarc info 弧的結(jié)點(diǎn)結(jié)構(gòu)（表結(jié)點(diǎn)） 2022/3/13 51 typedef struct VNode { VertexType data。 若是稀疏圖 (en2)，則比鄰接矩陣表示法 O(n2)省空間。 3. 用途： 鄰接矩陣多用于稠密圖的存儲（ e接近 n(n1)/2)； 而鄰接表多用于稀疏圖的存儲（ en2) 它是 有向圖 的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 } VexNode。 // 訪問標(biāo)記 int ivex, jvex。 EBox *firstedge。 ? 若 v的第 1個鄰接點(diǎn)沒訪問過，深度遍歷此鄰接點(diǎn)； ? 若當(dāng)前鄰接點(diǎn)已訪問過，再找 v的第 2個鄰接點(diǎn)重新遍歷。 for(w=FirstAdjVex(G, v)。} 2022/3/13 75 首先將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。 ++v) if (!visited[v]) DFS(G, v)。 V1 V2 V4 V5 V3 V7 V6 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 廣度遍歷： V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 廣度優(yōu)先搜索（遍歷）步驟： 簡單歸納： ? 在訪問了起始點(diǎn) v之后，依次訪問 v的鄰接點(diǎn)； ? 然后再依次 （順序） 訪問這些點(diǎn) （下一層） 中未被訪問過的鄰接點(diǎn)； ? 直到所有頂點(diǎn)都被訪問過為止。 v。 Visit(w)。 for(v=0。 //是第一棵樹的根 else qnextsibling=p。w=0。 //從第 w個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 G，建立子生成樹 q }//if }//DFSTree 從第 v個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖 G，建立以 T為根的生成樹 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度優(yōu)先生成森林 A B L M C F D E G H J K I A L M ^ ^ J ^ B ^ D ^ E ^ G ^ K ^ H ^ ^ I ^ ^ F ^ C ^ T 二、有向圖的強(qiáng)連通分量 深度優(yōu)先遍歷是求有向圖的強(qiáng)連通分量的一個有效方法，具體求解步驟如下： ⑴ 在有向圖中，從某個頂點(diǎn)出發(fā)進(jìn)行 深度優(yōu)先遍歷 ，并按其所有鄰接點(diǎn)的訪問都完成 （即 出棧 ）的順序?qū)㈨旤c(diǎn)排列起來。 該問題等價(jià)于： 2022/3/13 103 最小樹 MST性質(zhì) ? 假設(shè) N=(V,{E})是一個連通圖， U是頂點(diǎn)集 V的一個非空子集。 // 邊的權(quán)值 } closedge[MAX_VERTEX_NUM]。 ++i) { } 繼續(xù)向生成樹上添加頂點(diǎn) 。 考慮問題的出發(fā)點(diǎn) : 為使生成樹上 邊的權(quán)值之和達(dá)到最小 ，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。實(shí)現(xiàn)對相同子式的共享，節(jié)省存儲空間。 鄰接表結(jié)點(diǎn)： typedef struct node { int vex。 拓?fù)渑判蛩惴蚣? Status TopologicalSort(ALGraph G){ //有向圖 G采用鄰接表存儲結(jié)構(gòu) //若 G無回路，則輸出 G的頂點(diǎn)的一個拓?fù)湫蛄胁⒎祷?/OK，否則 ERROR。 printf(i, [i].data)。 }//TopologicalSort – 算法分析 建鄰接表： T(n)=O(e) 搜索入度為 0的頂點(diǎn)的時(shí)間： T(n)=O(n) 拓?fù)渑判颍?T(n)=O(n+e) 3 2 1 0 4 – 算法描述 例 1 2 3 4 5 6 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ top 1 6 top top 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 6 top top 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p=NULL 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 1 top top 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 top p 0 1 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 top p 4 0 1 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 p 4 top 0 1 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 p 4 top 0 0 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 p 4 top 3 0 0 0 2 in link 5。 //輸出 i號頂點(diǎn)并計(jì)數(shù) for (p=[i].Firstarc。 //對各頂點(diǎn)求入度 indegree[0..vernum1] InitStack(S)。 //鏈域 }JD。： 幾乎所有 工程 都可分為若干個稱為活動的 子工程 ，而這些子工程之間，通常受著一定條件的約束，如某些子工程的開始 必須在 另一子工程完成 之后。 k = i = 0。 // 求出加入生成樹的下一個頂點(diǎn) (k) printf(closedge[k].adjvex, [k])。 for ( j=0。 算法一：普里姆 （ Prim） 算法 算法二：克魯斯卡爾 ( Kruskal)算法 2022/3/13 104 取圖中任意一個頂點(diǎn) v 作為生成樹的根，之后往生成樹上添加新的頂點(diǎn) w。 ⑶ 每一次逆向深度優(yōu)先遍歷所訪問到的頂點(diǎn)集便是該有向圖的一個強(qiáng)連通分量的頂點(diǎn)集，若僅作一次逆向深度優(yōu)先遍歷就能訪問到圖的所有頂點(diǎn)，則該圖是強(qiáng)連通圖。//分配孩子結(jié)點(diǎn) *p={GetVex(G,w),NULL,NULL}。 //q指示當(dāng)前生成樹的根 DFSTree(G,v,p)。 ++v) visited[v]=FALSE。 // 訪問的頂點(diǎn) w入隊(duì)列 } // if } // while 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 1 0 1 2 3 4 5 f r 遍歷序列： 1 0 1 2 3 4 5 4 f r 遍歷序列： 1 4 0 1 2 3 4 5 4 3 f r 遍歷序列： 1 4 3 例 1 4 2 3 5 1 2 3 4 1 3 4 2 vexdata firstarc 5 5 4 3 ^ ^ ^ adjvex next 5 5 1 ^ 5 1 1 4 3 ^ 2 2 0 1 2 3 4 5 4 3 2 f r 遍歷序列： 1 4 3 2 0 1 2 3 4 5 3 2 f r 遍歷序列： 1 4 3 2 0 1 2 3 4 5 3 2 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 2 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5 5 f r 遍歷序列： 1 4 3 2 5 0 1 2 3 4 5