c語(yǔ)言程序設(shè)計(jì)第七章網(wǎng)(參考版)
2025-01-21 02:57本頁(yè)面
【正文】 A B C 6 4 2 11 3 D D(1) D(0) D(1) D(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 ∞ 0 3 7 0 3 7 0 3 7 0 P P(1) P(0) P(1) P(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 AB AC AB AC AB ABC AB ABC 1 BA BC BA BC BA BC BAC BC 2 CA CA CAB CA CAB CA CAB 0 4 11 6 0 2 3 ∞ 0 A B C A B C 0 1 2 。 } } } 求每一對(duì)頂點(diǎn)之間的最短路徑 弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑 。 P[w]=P[v]。amp。w。} final[v]=TRUE。++w) if(!final[w]) if(D[w]min) {v=w。 for(w=0。i。 fimal[v0]=TRUE。P[v][v]=TRUE。++w) P[v][w]=FALSE。 for(w=0。++v) { final[v]=FALSE。D) { for(v=0。 v0 v1 v2 v3 v4 v5 100 60 10 5 50 10 30 20 ∞ 10 ∞ 30 100 D 0 1 2 3 4 5 F F F F F F final 0 1 2 3 4 5 0 ∞ 10 ∞ 30 100 ∞ 0 5 ∞ ∞ ∞ ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ ∞ 20 0 60 ∞ ∞ ∞ ∞ ∞ 0 0 1 2 3 4 5 0 1 2 3 4 5 P 鄰接矩陣 T T60 T50 90 T 60TVoid ShortestPath_DIJ(MGraph G,int v0,PathMatrix amp。 假設(shè)求得最短路徑的頂點(diǎn)為 u， 若 Dist[u]+[u][k]Dist[k] 則將 Dist[k] 改為 Dist[u]+[u][k]。 1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。 求最短路徑的迪杰斯特拉算法： 一般情況下， Dist[k] = 源點(diǎn)到頂點(diǎn) k 的弧上的權(quán)值 或者 = 源點(diǎn)到 已求出最短路徑的頂點(diǎn) 的路徑長(zhǎng)度 + 已求出最短路徑的頂點(diǎn) 到頂點(diǎn) k 的 弧上的 權(quán)值 。 其余最短路徑的特點(diǎn)： 再下一條 路徑長(zhǎng)度次短 的最短路徑的特點(diǎn) : 它可能有三種情況：或者是 直接從源點(diǎn)到該點(diǎn) v3(只含一條弧 )； 或者是 從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v1，再到達(dá)該頂點(diǎn) (由兩條弧組成 )；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v2，再到達(dá)該頂點(diǎn) v3。 v2 這條路徑 必定是直接從源點(diǎn)到該點(diǎn) v1只含一條弧 ，并且這條弧的 權(quán)值最小。 tag=(ee==el)? ?*?:?? printf(j,k,dut,ee,el,tag)。 ee=ve[j]。p=pnextarc) { k=padjvex。++j) for(p=[j] .firstarc。 } for(j=0。 dut=*(pinfo)。 p。 vl[0.. ]=ve[]。 else return OK。 if(ve[j]+*(pinfo)=dut(j,k) ve[k]=ve[j]+*(pinfo)。 p=pnextarc) { k=padjvex。 for(p=[j].firstarc。Push(T,j)。 ve[0..]=0。 InitStack(T)。 Status TopologicalOrder(ALGraph G,Stack amp。 假設(shè)第 i 條弧為 j, k 則 對(duì)第 i 項(xiàng)活動(dòng)言 “活動(dòng) (弧 )”的 最早開(kāi)始時(shí)間 e(i) e(i) = ve(j)； “活動(dòng) (弧 )”的 最遲開(kāi)始時(shí)間 l(i) l(i) = vl(k) – dut(j,k)； 活動(dòng) ai的時(shí)間余量 ： l(i) e(i) 若 l[k] == e[k] 表示活動(dòng) ai是關(guān)鍵活動(dòng)。 整個(gè)工程完成的時(shí)間為 ：從有向圖的 源點(diǎn) 到 匯點(diǎn)的最長(zhǎng)路徑。 問(wèn)：哪些子工程項(xiàng)是“關(guān)鍵工程”？ 即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限的。 } } if(count) return ERROR。p=pnextarc) { k=padjvex。 for(p=[i].firstarc。 printf(i,[i].data)。 Count=0。i。 二、從有向圖中 刪去此頂點(diǎn)以及所 有以它為尾的弧 ； a b c g h d f e a b h c d g f e 在算法中需要用定量的描述替代定性的概念 沒(méi)有前驅(qū)的頂點(diǎn) ?? 入度為零的頂點(diǎn) 刪除頂點(diǎn)及以它為尾的弧 ?? 弧頭頂點(diǎn)的入度減 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)。 例如：對(duì)于下列有向圖 B D A C 可求得 拓?fù)溆行蛐蛄?： A B C D 或 A C B D 由此所得頂點(diǎn)的線性序列稱(chēng)之為拓?fù)溆行蛐蛄? B D A C 反之，對(duì)于下列有向圖 不能求得它的拓?fù)溆行蛐蛄小? 檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行 拓?fù)渑判?。 且 k++。 檢查邊集 E 中 第 i 條權(quán)值最小的邊 (u,v)。 k = i = 0。 考慮問(wèn)題的出發(fā)點(diǎn) : 為使生成樹(shù)上 邊的權(quán)值之和達(dá)到最小 ，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小。 ++j) //修改其它頂點(diǎn)的最小邊 if ([k][j].adj closedge[j].lowcost) closedge[j] = { [k], [k][j].adj }。 // 第 k頂點(diǎn)并入 U集 for (j=0。 // 求出加入生成樹(shù)的下一個(gè)頂點(diǎn) (k) printf(closedge[k].adjvex, [k])。 ++i) { } 繼續(xù)向生成樹(shù)上添加頂點(diǎn) 。 // 初始， U＝ {u} for (i=0。 ++j ) // 輔助數(shù)組初始化 if (j!=k) closedge[j] = { u, [k][j].adj }。 for ( j=0。 // 邊的權(quán)值 } closedge[MAX_VERTEX_NUM]。 一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件 : a b c d e g f 例如 : 19 5 14 18 27 16 8 21 3 12 7 所得生成樹(shù)權(quán)值和 = 14+8+3+5+16+21 = 67
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1