【正文】 //入度為零的頂點棧初始化 for ( int i = 0。u 如果輸出頂點個數(shù)少于 AOV網(wǎng)絡的頂點個數(shù) , 則報告網(wǎng)絡中存在有向環(huán)。n 拓撲排序算法可描述如下：u 建立入度為零的頂點棧 。 //建立邊結點 plink = [j].firstAdj。入度為零的頂點即無前驅頂點。這時網(wǎng)絡中必存在有向環(huán)。④ 重復以上 ② 、 ③ 步 , 直到216。n 例如 , 對學生選課工程圖進行拓撲排序 , 得到的拓撲有序序列為 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C270拓撲排序的方法① 輸入 AOV網(wǎng)絡 。即將各個頂點 (代表各個活動 )排列成一個線性有序的序列，使得AOV網(wǎng)絡中所有應存在的前驅和后繼關系都能得到滿足。 n 在 AOV網(wǎng)絡中不能出現(xiàn)有向回路 , 即有向環(huán)。這樣在有的課程之間有領先關系，有的課程可以并行地學習。除了很小的工程外，一般都把工程分為若干個叫做 “活動 ”的子工程。 } } 63 } //循環(huán) n1次 , 加入 n1條邊}n 分析以上算法 , 設連通網(wǎng)絡有 n 個頂點 , 則該算法的時間復雜度為 O(n2), 它適用于邊稠密的網(wǎng)絡。 j++ ) if ( nearvex[j] != 1 amp。 T[k++].cost = lowcost[v]。 // =1不參選 lowcost[j] min ) { v = j。 for ( int j = 0。 //存放最小生成樹結點的變量 for ( i = 0。 i++ ) { lowcost[i] = [u][i]。 T, int u ) { float * lowcost = new float[NumVertices]。u 取 lowcost[i] = min{ lowcost[i], Edge[v][i] }， 即用生成樹頂點集合外各頂點 i 到剛加入該集合的新頂點 v 的距離 Edge[v][i] 與原來它們到生成樹頂點集合中頂點的最短距離 lowcost[i] 做比較, 取距離近的作為這些集合外頂點到生成樹頂點集合內頂點的最短距離。 lowcost[i]最小的邊 , 用 v 標記它。n 采用鄰接矩陣作為圖的存儲表示 。n 構造最小生成樹的準則n 必須使用且僅使用該網(wǎng)絡中的 n1 條邊來聯(lián)結網(wǎng)絡中的 n 個頂點；n 不能使用產(chǎn)生回路的邊；n 各邊上的權值的總和達到最小。n 深度優(yōu)先生成樹的根是關節(jié)點的充要條件是它至少有兩個子女。n 在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關聯(lián)的邊時 , 也不破壞圖的連通性。圖的連通性問題41n 求連通分量的算法 需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。 } w = GetNextNeighbor (G, v, w)。 while ( w != 1 ) { //若鄰接頂點 w 存在 if ( !visited[w] ) { //未訪問過 cout GetValue (w) ‘ ’。 //進隊列 while ( ! QueueEmpty (amp。 InitQueue(amp。 ‥‥‥‥‥} 38void BFS (AdjGraph G, int v, int visited[ ] ) { cout GetValue (v) 39。n 為避免重復訪問 , 需要一個輔助數(shù)組 visited [ ]， 給被訪問過的頂點加標記。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點， … 如此做下去，直到圖中所有頂點都被訪問到為止。 //頂點 v 作訪問標記 int w = GetFirstNeighbor (G, v)。 i++ ) if ( ! visited[i] ) DFS (G, i, visited )。 i 。 如果沒有 , 就再退回一步進行搜索。 再從 w1 出發(fā) ,訪問與 w1鄰 接但還沒有訪問過的頂點 w2。n 圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。 pcost = weight。 28 //鏈入第 tail 號鏈表的前端 plink = [tail].firstAdj。 i++) { //逐條邊輸入 cin tail head weight。 i++) { cin [i].data。 //圖中當前的頂點個數(shù)與邊數(shù)} AdjGraph。 //頂點數(shù)據(jù)域 EdgeNode * firstAdj。 //目標頂點下標 EdgeData cost。//圖的種類標志}ALGraph。 // 指向第一條依附該頂點的弧 } VNode, AdjList[MAX_VERTEX_NUM]。// 指向下一條弧指針 InfoType *info。n 在鄰接表的邊鏈表中，各個邊結點的鏈入順序任意，視邊結點輸入次序而定。無向圖的鄰接表 同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊 (邊結點 ), 結點中有另一頂點的下標 dest 和指針 link。 // 該弧相關信息的指針adjvex nextarc info167。167。 //鄰接矩陣 , 可視為邊之間的關系 int n, e。 //頂點個數(shù)typedef char VertexData。01 2301215n 在有向圖中 , 統(tǒng)計第 i 行 1 的個數(shù)可得頂點 i 的出度，統(tǒng)計第 j 列 1 的個數(shù)可得頂點 j 的入度。 BACDF EBACDF E 12有 n個 頂點， n1條邊的圖必定是生成樹嗎？對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的 生成森林 。否則，其各個強連通子圖稱作它的 強連通分量。非強連通圖的極大強連通子圖叫做強連通分量。01 2301 2301 237AB EC F如 :從 A到 F長度為 3 的路徑 {A,B,C,F}8n 連通圖與連通分量 在無向圖中 , 若從頂點 v1到頂點 v2有路徑 , 則稱頂點 v1與 v2是連通的。AB EC F有向圖頂點的度 (TD)=出度 (OD)+入度 (ID)TD(B) =OD(B)+ID(B) = 3例如 :6n 路徑長度 非帶權圖的路徑長度是指此路徑上邊的條數(shù)。 則稱頂點序列 (vi vp1 vp2 ... vpm vj) 為從頂點 vi 到頂點 vj 的路徑。 在有向圖中 , 頂點的度等于該頂點的入度與出度之和。n 權 某些圖的邊具有與它相關的數(shù) , 稱之為權。有 n 個頂點的有向圖有n(n1) 條邊 , 則此圖為 有向完全圖 。 E2 表示從 x 到 y 的一條弧，且稱 x為弧尾， y為弧頭，這樣的圖稱為有向圖。v 圖的基本概念v 圖的存儲結構v 圖的遍歷v 圖的連通性問題 v 最小生成樹v 最短路徑 v 活動網(wǎng)絡第七章 圖1圖的基本概念167。 Path (x, y)} 其中， E1是頂點之間關系的有窮集合，也叫做邊 (edge)集合，此時的圖稱為無向圖。n 完全圖 若有 n 個頂點的無向圖有 n(n1)/2 條邊 , 則此圖為 無向完全圖 。 若 V’? V 且 E‘?E, 則稱 圖 G’ 是 圖 G 的子圖。記作 TD(v)。n 路徑 在圖 G＝ (V, E) 中 , 若從頂點 vi 出發(fā) , 沿一些邊經(jīng)過一些頂點 vp1, vp2, …, vpm， 到達頂點 vj。頂點的入度 : 以頂點 v為弧頭的弧的數(shù)目。n 簡單回路 若路徑上第一個頂點 v1 與最后一個頂點 vm 重合 , 則稱這樣的路徑為回路或環(huán)。n 強連通圖與強連通分量 在有向圖中 , 若對于每一對頂點 vi和 vj, 都存在一條從 vi到 vj和從 vj到 vi的路徑 , 則稱此圖是強連通圖。BACDF EBACDF E10有向圖 ,若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為 強連通圖 。在 極小連通子圖中去掉一條邊，則成為非連通圖。n 有向圖的鄰接矩陣可能是不對稱的。 //邊條數(shù)const int NumVertices = 10。 //頂點表 EdgeData Edge[NumVertices][NumVertices]。 鄰接表 :是圖的一種鏈式存儲結構。// 指向下一條弧指針 info。 //指向第一條依附該頂點的弧 19167。n 頂點 i 的邊鏈表的表頭指針 adj 在頂點表的下標為 i 的頂點記錄中，該記錄還保存了該頂點的其它信息。 // 該弧所指向的頂點的位置 struct ArcNode *nextarc。 // 頂點信息 ArcNode *firstarc。//圖的當前頂點數(shù)和弧數(shù)Int kind。 //邊上權值類型typedef struct node { //邊結點 int dest。鄰接表表示的圖的定義（為算法）26typedef struct { //頂點結點 VertexData data。 //鄰接表 int n, e。 i 。 i e。 pcost = weight。 pdest = tail。 }}29圖的遍歷n 從圖中某一頂點出發(fā)訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，這一過程就叫做圖的遍歷 (Traversing Graph)。n 兩種圖的遍歷方法 :u 深度優(yōu)先搜索 DFS (Depth First Search)u 廣度優(yōu)先搜索 BFS (Breadth First Search)31深度優(yōu)先搜索 DFS ( Depth First Search )n 深度優(yōu)先搜索過程67ACDEGBF IHACDEGBF IH1 2 3458 91 2 345678 9前進回退深度優(yōu)先生成樹32n DFS 在訪問圖中某