第6章圖(參考版)
2024-10-28 15:08本頁面
【正文】 滿足這種線性關(guān)系的序列稱為拓?fù)湫蛄? ? 拓?fù)渑判虻乃惴?基本步驟是： ? （ 1） 從網(wǎng)中選擇一個(gè)入度為 0的頂點(diǎn)并輸出； ? （ 2） 從網(wǎng)中刪除此頂點(diǎn)及其所有出邊 最短路徑和拓?fù)渑判? ? 拓?fù)渑判蛩惴枋鰹椋? ? topologicalsort(digraph) ? for i=l到 ? 尋找一個(gè)最小頂點(diǎn) v； ? num(v)=i； ? 從 digraph中刪除頂點(diǎn) v以及與 v相關(guān)聯(lián)的所有邊； 。重復(fù)上述過程，直至 S中包含所有的頂點(diǎn)。初始時(shí)， S中僅有一個(gè)源點(diǎn)， T中包含除源點(diǎn)外奉命頂點(diǎn)，此時(shí)各頂點(diǎn)的當(dāng)前最短路徑長度為源點(diǎn)到該頂點(diǎn)的弧上的權(quán)值。 ? 普里姆（ Prim）算法 ? 克魯斯卡爾（ Kruskal）算法 最短路徑和拓?fù)渑判? ? 最短路徑 ? 最短路徑問題，即求兩個(gè)頂點(diǎn)間長度最短的路徑 ? 路徑長度不是指路徑上邊數(shù)的總和，而是指路徑上各邊的權(quán)值總和 ? 單源路徑最短問題是指：對于給定的有向網(wǎng)絡(luò) G=(V,E)及單個(gè)源點(diǎn) v，求從 v到 G的其余各頂點(diǎn)的最短路徑。 圖的遍歷 ? 深度優(yōu)先搜索遍歷算法 （ 以隊(duì)列作為基本數(shù)據(jù)結(jié)構(gòu) ） 表示如下： ? breadthFirstSearch() ? for所有頂點(diǎn) u ? num(u)=0； ? edges=null； ? i=l； ? while存在一個(gè)頂點(diǎn) v使得 num(v)==0 ? num(v)=i++； ? enqueue(v)； //進(jìn)入隊(duì)列 ? while隊(duì)列非空 ? v=dequeue()； ? for所有和 v鄰接的頂點(diǎn) u ? if num(u)是 0 ? num(u)=i++； ? en
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1