第四部分 圖[8]

    弗洛伊德算法
　　void ShortestPath_FLOYD（Mgraph G PathMatrix &p[] distancMatrix &D）{
　　//用Floyd不著算法注有向網G中各對頂點V和W之間的最短路徑p[v][w]及其帶權
　　//限長度d[v][w]若p[v][w][u]為TRUE則U是從V到W當前求得最短路徑上的頂點
　　for（v=;v<Gvexnum;++v）
　　for（w=;w<Gvexnum;++W）{
　　D[v][w]=Garcs[v][w];
　　for（u=;u<Gvexnum;++u） p[v][w][u]=FALSE;
　　if（d[v][w]<INFINITY）{
　　P[v][w][v]=TRUE; P[v][w][w]=TRUE;
　　}//if
　　}//for
　　for（u=;u<Gvexnum;++u）
　　for（v=;v<Gvexnum;++v）
　　for（w=;w<Gvexnum;++w）
　　if{D[w][u]+D[u][w]<D[v][w]}
　　{D[v][w]=D[v][u]+D[u][w];
　　for（i=;i<Gvexnum;++i）
　　P[v][w][i]=P[v][w][i];
　　}//if
　　}//ShortestPath_FLOYD
　　
　　托普排序
　　
　　拓撲序列設G=（VE）是一個具有n個頂點的有向圖V中的頂點序列vv…vn稱為一個拓撲序列當且僅當滿足下列條件若從頂點vi到vj有一條路徑則在頂點序列中頂點vi必在頂點vj之前
　　
　　拓撲排序對一個有向圖構造拓撲序列的過程稱為拓撲排序
　　
　　基本思想
　　（）從AOV網中選擇一個沒有前驅的頂點並且輸出
　　（）從AOV網中刪去該頂點並且刪去所有以該頂點為尾的弧
　　（）重復上述兩步直到全部頂點都被輸出或AOV網中不存在沒有前驅的頂點

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23294.html