先上一波圖看看效果
DAG與AOV双饥？
DAG(Directed Acyclic Grap)指的是“有向無環(huán)圖”，通常也稱為“流程圖”迂苛。
當我們要完成一個工程的時候禁悠，我們可以先將大的工程分成幾個獨立的子工程欧啤，將子工程d當作“活動”睛藻，每個活動之間有先決條件的關系（時間上有著相互制約的關系），就是說活動的執(zhí)行有一定的順序邢隧。將“活動”看成頂點店印，以弧表示活動之間的優(yōu)先關系，這樣的圖稱為“AOV”網(wǎng)（Activity On Vertex NetWork）倒慧。
拓撲排序是什么吱窝，有什么用？
如果要執(zhí)行活動A迫靖，必須執(zhí)行活動B院峡，執(zhí)行B就要執(zhí)行C，要執(zhí)行C就要執(zhí)行A系宜，這樣形成一個環(huán)的話照激，就陷入了死循環(huán)，那我們怎么知道到底有沒有環(huán)呢盹牧？這時候就出現(xiàn)了拓撲排序俩垃，也就是說拓撲排序?qū)z測AOV圖中是否有環(huán)励幼，求一個有向圖拓撲排序序列的過程就是拓撲排序。
實現(xiàn)拓撲排序?qū)嵗?/h2>
先來看看用到的結(jié)構(gòu)體吧
#include <stdlib.h>
#include<stdio.h>
#define MAXVEX 20
#define NON -1
typedef char VexType;
typedef float AdjType;
/* 邊表中的結(jié)點 */
typedef struct EdgeNode {
int endvex; // 相鄰頂點字段 ,一條邊的另一個頂點
AdjType weight; //邊的權(quán)口柳，非帶權(quán)圖可以省略
struct EdgeNode *nextedge; // 鏈字段 ,連接到下一條邊
}*PEdgeNode, *EdgeList;
/*頂點中的信息*/
typedef struct {
VexType vertex; // 頂點信息
EdgeList edgelist; //后面所有的邊和組成的邊
} VexNode; // 頂點表中的結(jié)點
/*點的集合和邊表中鏈接信息構(gòu)成了圖*/
typedef struct {
int n; // 圖的頂點個數(shù)
VexNode vexs[MAXVEX];
} GraphList;
拓撲排序只需3步：
- 輸出頂點入度為0的值
- 讓這個點消失（刪除點及由它發(fā)出的邊）
- 重復執(zhí)行1和2直到輸出無連接邊的頂點
當然執(zhí)行這些之前苹粟，你得有個圖啊（攤手）跃闹，已經(jīng)有圖的童鞋請?zhí)^這一步嵌削。(下面是插入方法的主要代碼)
/*插入頂點及連接的信息*/
void insert(GraphList* p, int a, int b) {//a，b是將要連接的兩個頂點
EdgeList pp;//鏈接邊
//給頂點賦值
p->vexs[a].vertex = a;
//如果指向NON望艺，則說明是最后一個節(jié)點
if (b == NON)
{
p->vexs[a].edgelist = NULL;
return;
}
PEdgeNode temp;//邊的節(jié)點
temp = (PEdgeNode)malloc(sizeof(EdgeNode));
temp->endvex = b;
temp->nextedge = NULL;
pp = p->vexs[a].edgelist;//將連接邊復制給pp
if (pp == NULL)//連接兩個頂點
p->vexs[a].edgelist = temp;
else {//將新邊連接到后邊
while (pp->nextedge != NULL)
pp = pp->nextedge;
pp->nextedge = temp;
}
}
咳咳苛秕，現(xiàn)在開始拓撲排序了。
- 輸出頂點入度為0的值
首先你得找到哪些點入度為0(統(tǒng)計入度)
/*統(tǒng)計入度*/
Indegree = (int *)malloc(GL->n * sizeof(int));//存儲入度
for (i = 0; i<GL->n; i++)
Indegree[i] = 0;
for (i = 0; i < GL->n; i++)
{
EdgeList p = GL->vexs[i].edgelist;
while (p != NULL)
{
Indegree[p->endvex]++;
p = p->nextedge;
}
}//所有點的入度已經(jīng)存儲完畢
```
然后就把入度為0的頂點揪出來吧**(入度為0的揪出來放到stack里面)**
for (j = 0; j < GL->n; j++)//初始化stack棧
{
stack[j] = -1;
}
/*
*將入度為0的節(jié)點入棧
*/
for (i = 0; i < GL->n; i++)
{
if (Indegree[i] == 0)
{
stack[top] = i;
top++;
}
}
top--;//top在執(zhí)行完之后多加了一個
終于可以輸出入度為0的點了吧找默。
printf("%d ", GL->vexs[gettop].vertex);//輸出頂點自身
只有一句話嗎艇劫？
2. 讓已經(jīng)輸出的頂點就消失吧。
//輸出頂點信息以后減少相應鏈接點的入度惩激，標志著這個點從此消失
Indegree[GL->vexs[gettop].edgelist->endvex]--;
e = GL->vexs[gettop].edgelist->nextedge;
while (e != NULL)
{
Indegree[e->endvex]--;
e = e->nextedge;
}
當看到這里的時候店煞，就應該想如果最后一個頂點也這樣輸出的話，就會出現(xiàn)內(nèi)存泄露了风钻，所以當?shù)阶詈笠粋€頂點的時候浅缸，就特殊處理吧。
####然后通過循環(huán)就可以進行拓撲排序啦魄咕，別忘了用一個計數(shù)器來記錄輸出的個數(shù)，最后通過輸出的個數(shù)來判斷是否能進行拓撲排序蚌父。
