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