拓撲排序（Topological Sorting）
- 一、基本概念
- 二、拓撲排序的程序
- 三、拓撲排序的實作
- 1、設計資料結構
- 2、實作拓撲排序
前言：
對一項工程，我們最關心兩個問題：
1、工程能否順利完成；{拓撲排序）
2、整個工程完成所必需的最短工期;（關鍵路徑）
一、基本概念
1、有向無環圖：無環的有向圖，簡稱DAG圖（directed acycling graph）
作用：用來描述一項工程或者系統的進行程序，通常把計劃、施工、生產、程式流程等當成一個工程，一個工程都可以分成若干子工程（稱為活動），要完成整個工程，就要完成所有活動，而活動的執行通常是有某些先決條件的，即一些活動必須先于另一些活動完成，
2、AOV網：用一個有向圖表示一個工程的各子工程及其相互制約關系，其中以頂點表示活動，弧表示活動之間的優先制約關系，稱這種有向圖為頂點表示活動的網，簡稱AOV網，
3、AOV網的特點：
（1）若從i到j有一條有向路徑，則i是j的前驅，j是i的后繼
（2）若<i,j>是網中有向邊，則i是j的直接前驅，j是i的直接后繼
（3）AOV網中不應該有回路，因為如果有回路存在，則表明某項活動以自己為先決條件，顯然這是不符合邏輯的
（4）AOV網應該是一個有向無環圖，即DAG圖
4、拓撲排序（可以判斷一個有向圖是否存在環）：就是將AOV網中所有頂點排成一個線性序列（稱為拓撲序列），該序列滿足：
若在AOV網中由頂點vi到vj有一條路徑，則在該線性序列中的頂點vi必定在vj之前，
拓撲排序可以用來測驗AOV網是否有環：
1若網中所有頂點都在它的拓撲排序序列中，則該AOV網中必定不存在環，
2、如果有向圖存在環，則不能進行拓撲排序；反之，如果對一個有向圖不能進行拓撲排序，則必定存在環，
二、拓撲排序的程序
1、在有向圖中選一個無前驅的頂點且輸出它（即入度為0）
2、從圖中洗掉該頂點和所有以它為起點的邊
3、重復1、2，直至不存在無前驅的頂點
4、若此時輸出的頂點數小于有向圖的頂點數，則說明有向圖存在環，否則輸出的頂點序列為一個拓撲序列，
1、圖空：拓撲排序成功
2、圖不空，但找不到無前驅的頂點：有環拓撲排序的兩個基本操作：
1、計算每個頂點的入度：計算直接前驅個數
2、洗掉頂點所有的出邊：將該頂點的鄰接點的入度-1
三、拓撲排序的實作
1、設計資料結構
主要的存盤結構：以鄰接表存盤有向圖，因為洗掉邊用鄰接表比鄰接矩陣更有效，
輔助的存盤結構：
（1）一維陣列indegree[i]:存放各頂點入度，主要用于洗掉頂點，使得弧頭入度-1
（2）堆疊S：暫存所有入度為0的頂點，避免重復掃描陣列indegree檢測入度為0的頂點，提高演算法效率
（3）一維陣列topo[i]:記錄拓撲序列的頂點序號
2、實作拓撲排序
（1）、演算法思想：
（2）、演算法描述：
Status TopologicalSort(ALGraph G, int topo[])
{ //有向圖G采用鄰接表存盤
//若G無回路，則生成G的一個拓撲序列topo[]并回傳OK,否找ERROR
FindInDegree(G,indegree); //求出各頂點的入度存入陣列indegree中
InitStack(S); //堆疊初始化為空
for (i = 0i < G.vexnum;++i)
if (!indegree[i]) Push(S, i); //入度為0者進堆疊
m = 0; //對輸出頂點計數，初始化為0
while (!StackEmpty(S)) //堆疊S非空
{
Pop(S, i); //取堆疊頂頂點vi出堆疊
topo[m] = i; //將vi保存在拓撲序列陣列topo中
++m; //對輸出頂點計數
p = G.vertices[i].firstarc; //p指向vi的第一個鄰接點
while (p)
{
k = p->adjvex; //vk為vi的鄰接點
--indegree[k]; //vi的每個鄰接點的入度-1
if (indegree[k] == 0)
Push(S, k); //若入度減為0，則入堆疊
p = p->nextarc; //p指向頂點vi的下一個鄰接點
}
}
if (m < G.vexnum)
return ERROR; //該有向圖有回路
else
return OK;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/226910.html
標籤：其他
上一篇：性感荷官在線發牌，真的靠譜嗎？