有向無環(huán)圖的拓撲排序理解和算法
- 有向無環(huán)圖(DAG)定義
引用子維基百科的DAG定義, 在數(shù)學(xué)中，尤其是圖論和計算機科學(xué)中，DAG是一類不含環(huán)的有向圖(In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles). 對比之前的有向圖的強連通分量，凡是在圖中能能夠找到強連通分量的有向圖（單個頂點除外），都排除在DAG之外。對于有向無環(huán)圖，拓撲排序是其關(guān)鍵的操作，通過拓撲排序，便能把有向無環(huán)圖的先后遍歷順序”線性化“。
- DAG的應(yīng)用
現(xiàn)實世界中，很多場合都涉及到DAG的應(yīng)用，最常見的應(yīng)用包括，項目管理中各個事件先后順序排列的可行性，學(xué)校選課系統(tǒng)設(shè)計, 程序設(shè)計的互相依附以及事件的模擬等等。
我們以某高校的選課系統(tǒng)為例進行說明，如果要選擇Class H, 那么選修之前需要完成Class D 和 Class E課程，如果要選擇Class D課程，就需要提前學(xué)習(xí)Class A和 Class B.
選擇Class H的前置條件
- 拓撲排序目標(biāo)
在拓撲排序中，我們需要對有向無環(huán)圖每個頂點進行檢查，經(jīng)過拓撲排序后，我們會形成一個類似數(shù)組的線性結(jié)構(gòu)來表示各個頂點的先后順序，Dynamic Programming就需要利用DAG形成某些節(jié)點，對這些節(jié)點進行共用，減少計算事件。值得一提的是，拓撲排序的結(jié)果不一定唯一，同一個DAG圖形可能會有幾個不同的拓撲排序。我們以下圖為例，
最后形成的線性次序關(guān)系如下：
- 算法原理
一般實現(xiàn)Topological 排序方法有 Kahn’s 算法和 DFS算法，
- Kahn’s 算法非常直觀，兩步循環(huán)即可
? (1)在有向圖中選一個沒有前驅(qū)的頂點且輸出之
? (2)在圖中刪除該頂點和所有以它為尾的弧，換言之；對于圖上以此點為弧頭的頂點，其入度減1
? 重復(fù)上述兩步，直至全部頂點均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點為止（存在環(huán))
? 在Kahn’s 算法中：
? (a)可以直接線性搜索 入度為0的頂點（沒有前驅(qū))
? (b) 利用棧或隊列進行保留入度為0的頂點，后面直接出棧，更新相關(guān)頂點的入度值
? 兩類算法的事件復(fù)雜度分別為O(|V|2)和O(|V|+|E|).
-
DFS 算法當(dāng)有向圖中無環(huán)時，也可用DFS進行拓撲排序，因為圖中無環(huán)，則由圖中某點出發(fā)進行深度優(yōu)先搜索遍歷時，最先退出DFS函數(shù)的頂點即出度為零的頂點，是拓撲有序序列中的最后一個頂點?？梢岳脭?shù)組進行拓撲有序序列中的序號存儲。
? ? DFS算法實現(xiàn)
- 算法代碼實現(xiàn)
(a)可以直接線性搜索 入度為0的頂點（沒有前驅(qū))
/**
Use Adajacent list to go through each vertex
Work out the indegree array based on the traversal
*/
void assign_indegree(ALGraph G, int *indegree)
{
int i;
int v;
int w;
for(v=0;v<G.vexnum;v++)
{
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
indegree[w]++;
}
}
}
?
/**
Linear search the indegree array and return the first new zero indegree vertex node
*/
int find_new_zero_indegree_vertex(ALGraph G, int *indegree, int *top_num)
{
int i;
for(i=0;i<G.vexnum;i++)
{
if(top_num[i]==-1 && indegree[i]==0)
{
return i;
}
}
return NOT_A_VERTEX; //NOT_A_VERTEX=-1；
}
/**
Find the topological sort of directed graph
*/
Status topological_sort(ALGraph G,void (*visit)(VertexType e))
{
int counter;
int indegree[MAX_VERTEX_NUM];
int top_num[MAX_VERTEX_NUM]; //top_num will store the top order vertex #No.
int v;
int w;
for(counter=0;counter<G.vexnum;counter++)
{
*(top_num+counter)=-1;
}
memset(indegree,0,sizeof(int)*MAX_VERTEX_NUM);
assign_indegree(G,indegree);
for(counter=0;counter<G.vexnum;counter++)
{
v=find_new_zero_indegree_vertex(G,indegree,top_num);
//If v equals to NOT Available VERTEX,
//it must contain the cycle in the graph
//terminate the program
if(v==NOT_A_VERTEX)
{
return ERROR;
}
*(top_num+v)=counter;
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
indegree[w]--;
}
}
dispay_order(G,top_num,visit);
}
/**
Display the topological order based on top_num array list
*/
void dispay_order(ALGraph G, int *top_num, void (*visit)(VertexType e))
{
int i;
for(i=0;i<G.vexnum;i++)
{
visit(G.vertices[top_num[i]].data);
}
}
(b) 利用?；蜿犃羞M行保留入度為0的頂點，后面直接出棧，更新相關(guān)頂點的入度值
void assign_indegree(ALGraph G, int *indegree)
{
int i;
int v;
int w;
for(v=0;v<G.vexnum;v++)
{
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
indegree[w]++;
}
}
}
Status topological_sort(ALGraph G,void (*visit)(VertexType e))
{
SqStack S;
int indegree[MAX_VERTEX_NUM];
int i;
int v;
int w;
int count;
InitStack_Sq(&S);
memset(indegree,0,sizeof(int)*MAX_VERTEX_NUM);
assign_indegree(G,indegree);
count =0;
for(i=0;i<G.vexnum;i++)
{
if(!indegree[i])
{
Push_Sq(&S,i);
}
}
while(!StackEmpty_Sq(S))
{
Pop_Sq(&S,&v);
visit(G.vertices[v].data);
count++;
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if(!(--indegree[w]))
{
Push_Sq(&S,w);
}
}
}
if(count<G.vexnum)
{
return ERROR;
}
return OK;
}
? DFS算法實現(xiàn)
Status find_topological_sort(ALGraph G, int *ordering)
{
int v;
int w;
count =0;
int index;
memset(visited,0,sizeof(int)*MAX_VERTEX_NUM);
index=G.vexnum-1;
for(v=0;v<G.vexnum;v++)
{
if(!visited[v])
{
dfs_topological_sort(G,v,index-count,ordering);
}
}
if(count<G.vexnum)
{
return ERROR;
}
return OK;
}
//----
int dfs_topological_sort(ALGraph G, int v0, int index, int *ordering)
{
int v;
int w;
visited[v0]=1;
count++;
v=v0;
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if(!visited[w])
{
//index will be kept as the same as DFS deep dive into search
//when the first recursive call ended, it will be decremented by 1
//and in the next loop, index will be upated in the recursive call
index=dfs_topological_sort(G,w,index,ordering);
}
}
ordering[index]=v;
return index-1;
}
//------
void dispay_ordering(int *ordering, ALGraph G, void (*visit)(VertexType e))
{
int i;
for(i=0;i<G.vexnum;i++)
{
visit(G.vertices[ordering[i]].data);
}
}
- 總結(jié)
DAG的拓撲排序（全序）建立頂點或元素之間的先后關(guān)系，利用DAG的拓撲排序結(jié)果，可以有效地管理項目中不不同節(jié)點的先后順序，可以更合理地進行選課，抑或?qū)Υ笮统绦蛑g的依附關(guān)系進行羅列，做到邏輯次序先后合理，更好完成具體的應(yīng)用工作。
具體來說，如果對于某個事件或節(jié)點，其沒有任何前置約束，那么此事件或節(jié)點就可以作為當(dāng)前的拓撲有序點。拓撲排序算法一般分為Kahn’s 和經(jīng)典的DFS深度優(yōu)先搜索法，Kahn’s 比較直觀，DFS搜索法代碼簡練，各有千秋。
Reference book and video:
a)《數(shù)據(jù)結(jié)構(gòu)》 嚴(yán)蔚敏文章來源：http://www.zghlxwxcb.cn/news/detail-766664.html
b) Video, Topological Sort Algorithm|Graph Theory, William Fiset文章來源地址http://www.zghlxwxcb.cn/news/detail-766664.html
到了這里，關(guān)于有向無環(huán)圖的拓撲排序理解和算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
