【正文】 1）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。++v) { final[v]=FALSE。 fimal[v0]=TRUE。} final[v]=TRUE。 } } } 求每一對頂點之間的最短路徑 弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最短的路徑 。 P[w]=P[v]。++w) if(!final[w]) if(D[w]min) {v=w。P[v][v]=TRUE。D) { for(v=0。 求最短路徑的迪杰斯特拉算法： 一般情況下， Dist[k] = 源點到頂點 k 的弧上的權(quán)值 或者 = 源點到 已求出最短路徑的頂點 的路徑長度 + 已求出最短路徑的頂點 到頂點 k 的 弧上的 權(quán)值 。 ee=ve[j]。 dut=*(pinfo)。 if(ve[j]+*(pinfo)=dut(j,k) ve[k]=ve[j]+*(pinfo)。 ve[0..]=0。 整個工程完成的時間為 ：從有向圖的 源點 到 匯點的最長路徑。 for(p=[i].firstarc。 二、從有向圖中 刪去此頂點以及所 有以它為尾的弧 ； a b c g h d f e a b h c d g f e 在算法中需要用定量的描述替代定性的概念 沒有前驅(qū)的頂點 ?? 入度為零的頂點 刪除頂點及以它為尾的弧 ?? 弧頭頂點的入度減 1 a b c g h d f e 0 1 2 3 4 5 6 7 ? ? a b c d e f g h 2 6 6 7 3 4 6 4 5 5 ? ? ? ? ? ? 0 0 1 1 2 2 3 1 indegree 0 1 2 3 4 5 6 7 s a b 輸出次序 : b 02hh 1a 0 1 cc d 0d g f e 000 算法描述 Status Topologicalsort(ALGraph G) { FindinDegree(G,indegree)。 檢查邊集 E 中 第 i 條權(quán)值最小的邊 (u,v)。 // 第 k頂點并入 U集 for (j=0。 ++j ) // 輔助數(shù)組初始化 if (j!=k) closedge[j] = { u, [k][j].adj }。 此時 TE中必有 n1條邊 ， 則 T=(V,{TE})為 N的最小生成樹 。 EnQueue(Q, w)。 ++v ) if ( !visited[v]) { // v 尚未訪問 } } // BFSTraverse … … visited[u] = TRUE。 從圖中的某個頂點 V0出發(fā)，并在訪問此頂點之后 依次訪問 V0的所有 未被訪問 過的鄰接點 ，之后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使 “先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問 ，直至圖中所有和 V0有路徑相通的頂點都被訪問到。 for (v=0。 2. 如何判別 V的鄰接點是否被訪問？ a c b d e g f F F F F F F F T T T T T T T a c b d g f e 訪問標(biāo)志 : 訪問次序 : 例如 : 0 1 2 3 4 5 6 0 2 3 4 5 1 6 void DFS(Graph G, int v) { // 從頂點 v出發(fā)， 深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 頂點的結(jié)構(gòu)表示 typedef struct VexBox { VertexType data。 有向圖的結(jié)構(gòu)表示 (十字鏈表 ) A B C D A B C D 0 1 0 2 2 0 2 3 3 0 3 1 3 2 0 1 2 3 四、無向圖的鄰接多重表存儲表示 typedef struct Ebox { VisitIf mark。 struct ArcBox *hlink, *tlink。 // 頂點信息 ArcNode *firstarc。 1 4 2 3 0 1 2 0 1 2 3 4 A B C D E 有向圖的鄰接表 ? ? ? ? ? A B E C D 可見，在有向圖的鄰接表中不易找到指向該頂點的弧。 InfoType *info。 //在 G中刪除弧 v,w，若 G是無向的， //則還刪除對稱弧 w,v。 DeleteVex(amp。 // 返回 v 的“ 第一個鄰接點 ” 。G): // 銷毀圖 結(jié)構(gòu)的建立和銷毀 對頂點的訪問操作 LocateVex(G, u)。 簡單回路 :序列中第一個頂點和最后一個頂點相同的路徑。 15 9 7 21 11 3 2 弧或邊帶權(quán)的圖分別稱作 有向網(wǎng) 或無向網(wǎng) 。 Graph = (V , R ) 其中， R＝ {v,w| v,w∈ V 且 P(v,w)} v,w表示從 v 到 w 的一條弧，并稱 v 為弧頭， w 為弧尾。 和頂點 v 關(guān)聯(lián)的邊的數(shù)目定義為頂點 v的 度 。 A B E C F A B E C F 對有向圖， 否則，其各個強(qiáng)連通子圖稱作它的 強(qiáng)連通分量 。 // 返回 v 的值。 // 返回 v 的（相對于 w 的） “ 下一個鄰接 // 點 ”。 插入和刪除弧 InsertArc(amp。 BFSTraverse(G, v, Visit())。 AdjMatrix arcs。 3）在鄰接表上容易找到任一頂點的第一個鄰接點 和下一個鄰接點 4）設(shè)存儲頂點的一維數(shù)組大小為 n(圖的頂點數(shù) n), G占用存儲空間： n+e； G占用存儲空間與它的頂 點數(shù)和邊數(shù)有關(guān)；適用于邊稀疏的圖； typedef struct ArcNode { int adjvex。 int vexnum, arum。 ArcBox *firstin, *firstout。 InfoType *info。 無向圖的結(jié)構(gòu)表示 A B C D E 0 1 2 3 4 A B C D E 0 1 0 3 2 1 2 3 2 4 4 1 圖的遍歷 從圖中某個頂點出發(fā)游歷圖，訪遍 圖中其余頂點，并且使圖中的每個頂點 僅被訪問一次的過程。 w!=0。 // 訪問標(biāo)志數(shù)組初始化 for (v=0。 v。 // v入隊列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 求連通分量的算法需要對圖的每一個頂點進(jìn)行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量 。 // U集中的頂點 VRType lowcost。 i。 具體做法 : 先構(gòu)造一個只含 n 個頂點的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加 不使 SG 中產(chǎn)生回路 ，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n1 條邊為止。 } 普里姆算法 克魯斯卡爾算法 時間復(fù)雜度 O(n2) O(eloge) 稠密圖 稀疏圖 算法名 適應(yīng)范圍 比較兩種算法 拓?fù)渑判? 問題 : 假設(shè)以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。++i)