【正文】 到要求頂點 T[k].tail = nearvex[v]。 // =1不參選 lowcost[j] min ) { v = j。 j++ ) if ( nearvex[j] != 1 amp。 for ( int j = 0。 i++ ) if ( i != u ) { //循環(huán) n1次 , 加入 n1條邊 EdgeData min = MaxValue。 //存放最小生成樹結點的變量 for ( i = 0。 //及最短帶權路徑 }61 nearvex[u] = 1。 i++ ) { lowcost[i] = [u][i]。 for ( int i = 0。 T, int u ) { float * lowcost = new float[NumVertices]。 表示生成樹外頂點 i到生成樹內頂點 v當前距離最近。u 取 lowcost[i] = min{ lowcost[i], Edge[v][i] }， 即用生成樹頂點集合外各頂點 i 到剛加入該集合的新頂點 v 的距離 Edge[v][i] 與原來它們到生成樹頂點集合中頂點的最短距離 lowcost[i] 做比較, 取距離近的作為這些集合外頂點到生成樹頂點集合內頂點的最短距離。 0 28 ? ? ? 10 ? 1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 652u 將 nearvex[v] 改為 1, 表示它已加入生成樹頂點集合。 lowcost[i]最小的邊 , 用 v 標記它。n 例子50461322810251424221618 1251n 若選擇從頂點 0出發(fā)，即 u0 = 0， 則兩個輔助數(shù)組的初始狀態(tài)為：n 然后反復做以下工作：u 在 lowcost [ ]中選擇 nearvex[i] ? 1 amp。n 采用鄰接矩陣作為圖的存儲表示 。 以后每一步從一個頂點在 U 中 ,而另一個頂點不在 U 中的各條邊中選擇權值最小的邊 (u, v), 把它的頂點加入到集合 U 中。n 構造最小生成樹的準則n 必須使用且僅使用該網絡中的 n1 條邊來聯(lián)結網絡中的 n 個頂點；n 不能使用產生回路的邊；n 各邊上的權值的總和達到最小。45ABC DEFGHI J ABC DEFGHJABC DEFGHJII123456789 10根有兩 個子女關關節(jié)節(jié)點點關關節(jié)節(jié)點點關節(jié)點關節(jié)點46ABC DEFGHI JAB HID FBC DEFGH連通圖和它的連通分量47最小生成樹 ( minimum cost spanning tree )n 使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。n 深度優(yōu)先生成樹的根是關節(jié)點的充要條件是它至少有兩個子女。44n 在一個無向連通圖 G中 , 重連通分量可以利用深度優(yōu)先生成樹找到。n 在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關聯(lián)的邊時 , 也不破壞圖的連通性。42AC D E IBF OGHJNMLK非連通無向圖的三個連通分量A H KC D E IBF OG JNML非連通圖的連通分量的極小連通子圖43重連通分量 (Biconnected Component)n 在無向連通圖 G中 , 當且僅當刪去 G中的頂點 v及所有依附于 v的所有邊后 , 可將圖分割成兩個或兩個以上的連通分量，則稱頂點 v為關節(jié)點。圖的連通性問題41n 求連通分量的算法 需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。 }40 連通分量 (Connected ponent)n 當無向圖為非連通圖時 , 從圖中某一頂點出發(fā) , 利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點 , 只能訪問到該頂點所在的最大連通子圖 (連通分量 )的所有頂點。 } w = GetNextNeighbor (G, v, w)。 EnQueue (amp。 while ( w != 1 ) { //若鄰接頂點 w 存在 if ( !visited[w] ) { //未訪問過 cout GetValue (w) ‘ ’。q, v)。 //進隊列 while ( ! QueueEmpty (amp。 EnQueue (amp。 InitQueue(amp。 visited[v] = 1。 ‥‥‥‥‥} 38void BFS (AdjGraph G, int v, int visited[ ] ) { cout GetValue (v) 39。 i 。n 為避免重復訪問 , 需要一個輔助數(shù)組 visited [ ]， 給被訪問過的頂點加標記。因此 , 廣度優(yōu)先搜索不是一個遞歸的過程。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點， … 如此做下去，直到圖中所有頂點都被訪問到為止。 //若 頂點 w 未訪問過 , 遞歸訪問頂點 w w = GetNextNeighbor (G, v, w )。 //頂點 v 作訪問標記 int w = GetFirstNeighbor (G, v)。 //釋放 visited }34void DFS (AdjGraph G, int v, int visited [ ] ) { cout GetValue (G, v) ‘ ’。 i++ ) if ( ! visited[i] ) DFS (G, i, visited )。 //訪問數(shù)組 visited 初始化 for ( int i = 0。 i 。33 圖的深度優(yōu)先搜索算法void Graph_Traverse (AdjGraph G) { int * visited = new int [NumVertices]。 如果沒有 , 就再退回一步進行搜索。接著 , 退回一步 , 退到前一次剛訪問過的頂點 , 看是否還有其它沒有被訪問的鄰接頂點。 再從 w1 出發(fā) ,訪問與 w1鄰 接但還沒有訪問過的頂點 w2。30n 輔助數(shù)組 visited [ ] 的初始狀態(tài)為 0, 在圖的遍歷過程中 , 一旦某一個頂點 i 被訪問 , 就立即讓 visited [i] 為 1, 防止它被多次訪問。n 圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。 [head].firstAdj = p。 pcost = weight。 p = new EdgeNode。 28 //鏈入第 tail 號鏈表的前端 plink = [tail].firstAdj。 pdest = head。 i++) { //逐條邊輸入 cin tail head weight。 } for ( i = 0。 i++) { cin [i].data。 //輸入頂點個數(shù)和邊數(shù) for ( int i = 0。 //圖中當前的頂點個數(shù)與邊數(shù)} AdjGraph。 typedef struct { //圖的鄰接表 VertexNode VexList [NumVertices]。 //頂點數(shù)據(jù)域 EdgeNode * firstAdj。 //下一邊鏈接指針} EdgeNode。 //目標頂點下標 EdgeData cost。 //頂點數(shù)據(jù)類型typedef int EdgeData。//圖的種類標志}ALGraph。Int vexnum,arum。 // 指向第一條依附該頂點的弧 } VNode, AdjList[MAX_VERTEX_NUM]。typedef struct VNode { VertexType data。// 指向下一條弧指針 InfoType *info。 23圖的鄰接表存儲表示define MAX_VERTEX_NUM 20typedef struct ArcNode { int adjvex。n 在鄰接表的邊鏈表中，各個邊結點的鏈入順序任意，視邊結點輸入次序而定。 有向圖的鄰接表和逆鄰接表ABCdata adjABC012dest linkdest link?鄰接表 (出邊表 )data adjABC012dest link逆鄰接表 (入邊表 )10 2?????01121n 網絡 (帶權圖 ) 的鄰接表BACD695 28data adjABCD0123dest cost link????1 5 3 62 83 21 9(出邊表 )(頂點表 )22n 帶權圖的邊結點中保存該邊上的權值 cost。無向圖的鄰接表 同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊 (邊結點 ), 結點中有另一頂點的下標 dest 和指針 link。 // 頂點信息firstarc。 // 該弧相關信息的指針adjvex nextarc info167。 // 該弧所指向的頂點的位置nextarc。167。 用鄰接矩陣表示的結構定義18鄰接表 (Adjacency List)167。 //鄰接矩陣 , 可視為邊之間的關系 int n, e。 //邊上權值類型typedef struct { VertexData vexList[NumVertices]。 //頂點個數(shù)typedef char VertexData。161863 29 542031網絡的鄰接矩陣17define MaxValue Int_Maxconst int NumEdge