拓?fù)渑判蚪榻B
我們會把施工過程唱凯、生產(chǎn)流程、軟件開發(fā)么鹤、教學(xué)安排等都當(dāng)成一個項(xiàng)目工程來對待，所有的工程都可分為若干個“活動”的子工程味廊。例如下圖一張簡陋的電影制作流程圖蒸甜，現(xiàn)實(shí)中可能并不完全相同，但基本表達(dá)了一個工程和若干個活動的概念余佛。在這些活動之間柠新，通常會受到一定的條件約束，如其中某些活動必須在另一些活動完成之后才能開始辉巡。就像電影制作不可能在人員到位進(jìn)駐場地時恨憎，導(dǎo)演還沒有找到，也不可能在拍攝過程中，場地都沒有憔恳。這都會導(dǎo)致荒謬的結(jié)果瓤荔。因此這樣的工程圖，一定是無環(huán)的有向圖钥组。
在一個表示工程的有向圖中输硝，用頂點(diǎn)表示活動，用弧表示活動之間的優(yōu)先關(guān)系程梦，這樣的有向圖為頂點(diǎn)表示活動的網(wǎng)点把，我們稱為AOV網(wǎng)（ActivityOn Vertex Network）。AOV網(wǎng)中的弧表示活動之間存在的某種制約關(guān)系作烟。比如演職人員確定了愉粤，場地也聯(lián)系好了，才可以開始進(jìn)場拍攝拿撩。另外就是AOV網(wǎng)中不能存在回路衣厘。剛才已經(jīng)舉了例子，讓某個活動的開始要以自己完成作為先決條件压恒，顯然是不可以的影暴。
設(shè)G=(V,E)是一個具有n個頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1型宙，v2，……伦吠，vn妆兑，滿足若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前毛仪。則我們稱這樣的頂點(diǎn)序列為一個拓?fù)湫蛄小?/p>
上圖這樣的AOV網(wǎng)的拓?fù)湫蛄胁恢挂粭l搁嗓。序列v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 是一條拓?fù)湫蛄校鴙0 v1 v4 v3 v2 v7 v6 v5 v8 v10 v9 v12 v11 v14 v13 v15 v16也是一條拓?fù)湫蛄小?/p>
所謂拓?fù)渑判蛳溲ィ鋵?shí)就是對一個有向圖構(gòu)造拓?fù)湫蛄械倪^程腺逛。構(gòu)造時會有兩個結(jié)果，如果此網(wǎng)的全部頂點(diǎn)都被輸出衡怀，則說明它是不存在環(huán)（回路）的AOV網(wǎng)棍矛；如果輸出頂點(diǎn)數(shù)少了，哪怕是少了一個抛杨，也說明這個網(wǎng)存在環(huán)（回路）够委，不是AOV網(wǎng)。
拓?fù)渑判蛩惴?/h1>
對AOV網(wǎng)進(jìn)行拓?fù)渑判虻幕舅悸肥牵簭腁OV網(wǎng)中選擇一個入度為0的頂點(diǎn)輸出怖现，然后刪去此頂點(diǎn)茁帽，并刪除以此頂點(diǎn)為尾的弧，繼續(xù)重復(fù)此步驟，直到輸出全部頂點(diǎn)或者AOV網(wǎng)中不存在入度為0的頂點(diǎn)為止脐雪。
首先我們需要確定一下這個圖需要使用的數(shù)據(jù)結(jié)構(gòu)厌小。前面求最小生成樹和最短路徑時，我們用的都是鄰接矩陣战秋，但由于拓?fù)渑判虻倪^程中璧亚，需要刪除頂點(diǎn)，顯然用鄰接表會更加方便脂信。因此我們需要為AOV網(wǎng)建立一個鄰接表癣蟋。考慮到算法過程中始終要查找入度為0的頂點(diǎn)狰闪，我們在原來頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)中疯搅，增加一個入度域in，結(jié)構(gòu)如下表所示埋泵，其中in就是入度的數(shù)字幔欧。
| in | data | first | edge |
|---|---|---|---|
因此對于下圖的第一幅圖AOV網(wǎng)，我們可以得到如第二幅圖的鄰接表數(shù)據(jù)結(jié)構(gòu)丽声。
在拓?fù)渑判蛩惴ㄖ薪刚幔婕暗慕Y(jié)構(gòu)代碼如下。
/* 邊表結(jié)點(diǎn) */
typedef struct EdgeNode
{
/* 鄰接點(diǎn)域雁社，存儲該頂點(diǎn)對應(yīng)的下標(biāo) */
int adjvex;
/* 用于存儲權(quán)值浴井，對于非網(wǎng)圖可以不需要 */
int weight;
/* 鏈域，指向下一個鄰接點(diǎn) */
struct EdgeNode *next;
} EdgeNode;
/* 頂點(diǎn)表結(jié)點(diǎn) */
typedef struct VertexNode
{
/* 頂點(diǎn)入度*/
int in;
/* 頂點(diǎn)域霉撵，存儲頂點(diǎn)信息 */
int data;
/* 邊表頭指針 */
EdgeNode *firstedge;
} VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
/* 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */
int numVertexes,numEdges;
} graphAdjList, *GraphAdjList;
在算法中磺浙，我還需要輔助的數(shù)據(jù)結(jié)構(gòu)—棧，用來存儲處理過程中入度為0的頂點(diǎn)徒坡，目的是為了避免每個查找時都要去遍歷頂點(diǎn)表找有沒有入度為0的頂點(diǎn)撕氧。
/* 拓?fù)渑判颍鬐L無回路崭参，則輸出拓?fù)渑判蛐蛄胁⒎祷豋K呵曹，若有回路返回ERROR */
Status TopologicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i, k, gettop;
/* 用于棧指針下標(biāo) */
int top = 0;
/* 用于統(tǒng)計(jì)輸出頂點(diǎn)的個數(shù) */
int count = 0;
/* 建棧存儲入度為0的頂點(diǎn) */
int *stack;
stack = (int *)malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
if (GL->adjList[i].in == 0)
/* 將入度為0的頂點(diǎn)入棧 */
stack[++top] = i;
while (top != 0)
{
/* 出棧 */
gettop = stack[top--];
/* 打印此頂點(diǎn) */
printf("%d -> ", GL->adjList[gettop].data);
/* 統(tǒng)計(jì)輸出頂點(diǎn)數(shù) */
count++;
/* 對此頂點(diǎn)弧表遍歷 */
for (e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k = e->adjvex;
/* 將k號頂點(diǎn)鄰接點(diǎn)的入度減1 */
if (!(--GL->adjList[k].in))
/*若為0則入棧款咖，以便于下次循環(huán)輸出 */
stack[++top] = k;
}
}
/*如果count小于頂點(diǎn)數(shù)何暮，說明存在環(huán) */
if (count < GL->numVertexes)
return ERROR;
else
return OK;
}
1．程序開始運(yùn)行，第3～7行都是變量的定義铐殃，其中stack是一個棧海洼，用來存儲整型的數(shù)字。
2．第8～10行富腊，作了一個循環(huán)判斷坏逢，把入度為0的頂點(diǎn)下標(biāo)都入棧，從下圖的右圖鄰接表可知，此時stack應(yīng)該為：{0,1,3}是整，即v0肖揣、v1、v3的頂點(diǎn)入度為0浮入，如下圖所示龙优。
3．第12～23行，while循環(huán)事秀，當(dāng)棧中有數(shù)據(jù)元素時彤断，始終循環(huán)。
4．第14～16行易迹，v3出棧得到gettop=3宰衙。并打印此頂點(diǎn)，然后count加1睹欲。
5．第17～22行供炼，循環(huán)其實(shí)是對v3頂點(diǎn)對應(yīng)的弧鏈表進(jìn)行遍歷，即下圖中的灰色部分窘疮，找到v3連接的兩個頂點(diǎn)v2和v13劲蜻，并將它們的入度減少一位，此時v2和v13的in值都為1考余。它的目的是為了將v3頂點(diǎn)上的弧刪除先嬉。
6．再次循環(huán)，第12～23行楚堤。此時處理的是頂點(diǎn)v1疫蔓。經(jīng)過出棧、打印身冬、count=2后衅胀，我們對v1到v2、v4酥筝、v8的弧進(jìn)行了遍歷滚躯。并同樣減少了它們的入度數(shù)，此時v2入度為0嘿歌，于是由第20～21行知掸掏，v2入棧，如下圖所示宙帝。試想丧凤，如果沒有在頂點(diǎn)表中加入in這個入度數(shù)據(jù)域，20行的判斷就必須要是循環(huán)步脓，這顯然是要消耗時間的愿待，我們利用空間換取了時間浩螺。
7．接下來，就是同樣的處理方式了仍侥。下圖展示了v2 v6 v0 v4 v5 v8的打印刪除過程要出，后面還剩幾個頂點(diǎn)都類似，就不圖示了农渊。
8．最終拓?fù)渑判虼蛴〗Y(jié)果為3->1->2->6->0->4->5->8->7->12->9->10->13->11厨幻。當(dāng)然這結(jié)果并不是唯一的一種拓?fù)渑判蚍桨浮?/p>
分析整個算法，對一個具有n個頂點(diǎn)e條弧的AOV網(wǎng)來說腿时，第8～10行掃描頂點(diǎn)表况脆，將入度為0的頂點(diǎn)入棧的時間復(fù)雜為O(n)，而之后的while循環(huán)中批糟，每個頂點(diǎn)進(jìn)一次棧格了，出一次棧，入度減1的操作共執(zhí)行了e次徽鼎，所以整個算法的時間復(fù)雜度為O(n+e)盛末。
