第6章圖-資料下載頁
2025-10-15 15:08本頁面
【導讀】集集合，邊是頂點偶對。個結點有任意多個前驅(qū)和后繼結點。，Vm到達Vg則稱頂點序列（VP，V1，1．圖中各頂點序號確定后，圖的鄰接矩陣是唯一確定的；2．無向圖和無向網(wǎng)的鄰接矩陣是一個對稱矩陣；4．有向圖鄰接矩陣第i行非0元素個數(shù)為第i個頂點的出度，第i列非0. 并對圖中每上頂點vi建立一個單鏈表，1．對應于鄰接矩陣的每一行有一個線形鏈接表；5．對于有向圖：非零元素則表示該行頂點為起點的一條邊的終點。歷開始的頂點，就結束遍歷過程。點，直到所有頂點均被訪問過為止。最短路徑問題，即求兩個頂點間長度最短。路徑長度不是指路徑上邊數(shù)的總和，而是
【正文】 是指：對于給定的有向網(wǎng)絡 G=(V,E)及單個源點 v，求從 v到 G的其余各頂點的最短路徑。 最短路徑和拓撲排序 ? 迪卡斯特拉（ Dijkstra）算法 基本思想是：設置兩個頂點集 S和 T， S中存放已確定最短路徑的頂點， T中存放待確定最短路徑的頂點。初始時， S中僅有一個源點， T中包含除源點外奉命頂點，此時各頂點的當前最短路徑長度為源點到該頂點的弧上的權值。接著選取 T中當前最短路徑長度最小的一個頂點 v加入 S，然后修改 T中剩余頂點的當前最短路徑長度，修改的原則是：當 v的最短路徑長度與 v到 T中的頂點之間的權值之和小于該頂點的當前最短路徑長度時，用前者替換后者。重復上述過程，直至 S中包含所有的頂點。 最短路徑和拓撲排序 ? 迪卡斯特拉 （ Dijkstra） 算法偽碼描述如下： ? S={v}； ? 置 T中各頂點的距離值； ? while S中頂點數(shù) n ? { ? 在 T中選擇距離值最小的頂點 u； ? S=S+{u}； ? 調(diào)整 T中剩余頂點的距離值； ? } 最短路徑和拓撲排序 ? 拓撲排序 ? 拓撲排序 :對于一個 AOV網(wǎng)，通常需要把它的所有頂點排成一個滿足下述關系的線性序列 v1，v2， … ， vn，如果 AOV網(wǎng)中從頂點 vi到頂點 vj有一條路徑，則在該線性序列中頂點 vi必在頂點 vj之前。滿足這種線性關系的序列稱為拓撲序列 ? 拓撲排序的算法 基本步驟是： ? （ 1） 從網(wǎng)中選擇一個入度為 0的頂點并輸出； ? （ 2） 從網(wǎng)中刪除此頂點及其所有出邊 最短路徑和拓撲排序 ? 拓撲排序算法描述為： ? topologicalsort(digraph) ? for i=l到 ? 尋找一個最小頂點 v； ? num(v)=i； ? 從 digraph中刪除頂點 v以及與 v相關聯(lián)的所有邊；
教學課件相關推薦
鄂ICP備17016276號-1