aov數據結構演算法

『壹』 數據結構，這個帶權圖的拓撲排序什麼思路

由AOV網構造拓撲序列的拓撲排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。
(1) 選擇一個入度為0的頂點並輸出之；
(2) 從網中刪除此頂點及所有出邊。

就是輸出所有箭頭都向外指的節點，然後刪除與該節點相連的邊，一直循環直到節點都輸出或不能夠找到這樣的節點。
顯然，拓撲排序不一定唯一。

題目的一種拓撲排序：
S,G,D,A,B,H,E,I,F,C,T

『貳』 求詳解 pascal 拓撲排序

拓撲排序
有向無迴路圖又稱為dag。對這種有向無迴路圖的拓撲排序的結果為該圖所有頂點的一個線性序列，滿足如果G包含(u,v)，則在序列中u出現在v之前（如果圖是有迴路的就不可能存在這樣的線性序列)。一個圖的拓撲排序可以看成是圖的所有頂點沿水平線排成的一個序列，使得所有的有向邊均從左指向右。因此，拓撲排序不同於通常意義上對於線性表的排序。

有向無迴路圖經常用於說明事件發生的先後次序，圖1給出一個實例說明早晨穿衣的過程。必須先穿某一衣物才能再穿其他衣物(如先穿襪子後穿鞋)，也有一些衣物可以按任意次序穿戴(如襪子和短褲)。圖1(a)所示的圖中的有向邊(u,v)表明衣服u必須先於衣服v穿戴。因此該圖的拓撲排序給出了一個穿衣的順序。每個頂點旁標的是發現時刻與完成時刻。圖1(b)說明對該圖進行拓撲排序後將沿水平線方向形成一個頂點序列，使得圖中所有有向邊均從左指向右。

下列簡單演算法可以對一個有向無迴路圖進行拓撲排序。

procere Topological_Sort(G);
begin
1.調用DFS(G)計算每個頂點的完成時間f[v];
2.當每個頂點完成後，把它插入鏈表前端;
3.返回由頂點組成的鏈表;
end;
圖1(b)說明經拓撲排序的結點以與其完成時刻相反的順序出現。因為深度優先搜索的運行時間為θ(V+E)，每一個v中結點插入鏈表需佔用的時間為θ(1)，因此進行拓撲排序的運行時間θ(V+E)。

圖1 早晨穿衣的過程

為了證明演算法的正確性，我們運用了下面有關有向無迴路圖的重要引理。

引理1

有向圖G無迴路當且僅當對G進行深度優先搜索沒有得到反向邊。

證明：

→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。

←：假設G中包含一迴路C，我們證明對G的深度優先搜索將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。(證畢)

定理1

Topological_Sort(G)演算法可產生有向無迴路圖G的拓撲排序。

證明:

假設對一已知有問無迴路圖G=(V,E)運行過程DFS以確定其結點的完成時刻。那麼只要證明對任一對不同結點u,v∈V，若G中存在一條從u到v的有向邊，則f[v]<f[u]即可。考慮過程DFS(G)所探尋的任何邊(u,v)，當探尋到該邊時，結點v不可能為灰色，否則v將成為u的祖先，(u,v)將是一條反向邊，和引理1矛盾。因此，v必定是白色或黑色結點。若v是白色，它就成為u的後裔，因此f[v]<f[u]。若v是黑色，同樣f[v]<f[u]。這樣一來對於圖中任意邊(u,v)，都有f[v]<f[u]，從而定理得證。（證畢）

另一種拓撲排序的演算法基於以下思想：首先選擇一個無前驅的頂點（即入度為0的頂點，圖中至少應有一個這樣的頂點，否則肯定存在迴路），然後從圖中移去該頂點以及由他發出的所有有向邊，如果圖中還存在無前驅的頂點，則重復上述操作，直到操作無法進行。如果圖不為空，說明圖中存在迴路，無法進行拓撲排序；否則移出的頂點的順序就是對該圖的一個拓撲排序。

下面是該演算法的具體實現：

procere Topological_Sort_II(G);
begin
1 for 每個頂點u∈V[G] do d[u]←0; //初始化d[u],d[u]用來記錄頂點u的入度

2 for 每個頂點u∈V[G] do
3 for 每個頂點v∈Adj[u] do d[v]←d[v]+1; //統計每個頂點的入度

4 CreateStack(s); //建立一個堆棧s

5 for 每個頂點u∈V[G] do
6 if d[u]=0 then push(u,s); //將度為0的頂點壓入堆棧

7 count←0;

8 while (not Empty(s)) do
begin
9 u←top(s); //取出棧頂元素
10 pop(s); //彈出一個棧頂元素
11 count←count+1;
12 R[count]←u; //線性表R用來記錄拓撲排序的結果

13 for 每個頂點v∈Adj[u] do //對於每個和u相鄰的節點v
begin
14 d[v]←d[v]-1;
15 if d[v]=0 then push(v,s); //如果出現入度為0的頂點將其壓入棧
end;
end;

16 if count<>G.size then writeln('Error! The graph has cycle.')
17 else 按次序輸出R;
end;
上面的演算法中利用d[u]來記錄頂點u的入度，第2-3行用來統計所有頂點的入度，第5-6行將入度為0的頂點壓入堆棧，第8-15行不斷地從棧頂取出頂點，將該頂點輸出到拓撲序列中，並將所有與該頂點相鄰的頂點的入度減1，如果某個頂點的入度減至0，則壓入堆棧，重復該過程直到堆棧空了為止。顯而易見該演算法的復雜度為O(VE)，因為第2-3行的復雜性就是O(VE)，後面8-15行的復雜性也是O(VE)。這個演算法雖然簡單，但是沒有前面一個演算法的效率高。

『叄』 求拓撲排序演算法的詳細講解

3.1AOV網

在現代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在有向圖中若以頂點表示活動，有向邊表示活動之間的先後關系，這樣的圖簡稱為AOV網。如下圖是計算機專業課程之間的先後關系：

基礎知識課程應先於其它所有課程，pascal語言課程應先於數據結構。

3. 2 拓撲排序

在AOV網中為了更好地完成工程，必須滿足活動之間先後關系，需要將各活動排一個先後次序即為拓撲排序。如上圖的拓撲排序

基礎知識；Pascal；數據結構；離散數學。或

基礎知識；離散數學Pascal；數據結構。

拓撲排序的方法和步驟：

（1）在圖中選一個沒有前趨的頂點並輸出之

（2）刪除該頂點及由它發出的各邊，直到圖中不存在沒有前趨的頂點為止。

若圖中存在迴路，拓撲排序無法進行。

以下是將一AOV網進行拓撲排序的演算法：

網採用鄰接矩陣A表示,若a[i，j]=1，表示活動i先於j，a[i，j]=0，表示活動i與j不存在先後關系。

（1）計算各頂點的入度

（2）找入度為零的點輸出之，刪除該點，且與該點關聯各點的入度減1

（3）若所有頂點都輸出完畢。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
procere init;
var
i,j:integer;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(map[i,j]);
inc(into[j]);
end;
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

3.3應用舉例與練習

例：士兵排隊問題：

有N個士兵（1<=N<=100),編號依次為1,2,...,N.隊列訓練時，指揮官要把士兵從高到矮排成一行，但指揮官只知道「1 比2 高，7 比 5高」這樣的比較結果。

輸入文件：第一行為數N（N〈=100）；表示士兵的個數。以下若干行每行兩個數A，B 表示A高於B。

輸出文件：給出一個合法的排隊序列。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
fp:text;
procere init;
var
i,j:integer;
begin
assign(fp,'tp.txt');
reset(fp);
readln(fp,n);
fillchar(map,sizeof(map),0);
fillchar(into,sizeof(into),0);
while not(seekeof(fp)) do
begin
readln(fp,i,j);
map[i,j]=1 ;
inc(into[j]);
end;
close(fp);
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

練習：

Z語言問題：Z語言的基本字母也是26個，不妨用a到z表示，但先後順序與英語不同。

現在按Z語言的順序給出了N個單詞，請依照這些單詞給出一個可能的Z語言字母順序。

輸入文件：第一行一個數N（N<=100)表示單詞的個數。

第二行到第N+1行，每行一個單詞。

輸出文件：僅一行，可能的字母順序。

(圖不好粘貼）

『肆』 數據結構用什麼方法來判斷有向圖是否存在迴路

數據結構中用拓撲排序來判斷有向圖是否存在迴路。

用頂點表示活動、邊表示活動間先後關系的有向圖稱做頂點活動網（AOV網）。一個AOV網應該是一個有向無環圖，即不應該帶有迴路，因為若帶有迴路，則迴路上的所有活動都無法進行。

在AOV網中，若不存在迴路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，數據結構中把此序列叫做拓撲序列，由AOV網構造拓撲序列的過程叫做拓撲排序。

綜上，若一個有向圖中存在拓撲排序，則有向圖中不存在迴路。

(4)aov數據結構演算法擴展閱讀：

在有向圖進行拓撲排序的演算法思想：

由AOV網構造拓撲序列的拓撲排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。

1、選擇一個入度為0的頂點並輸出之；

2、從網中刪除此頂點及所有出邊。

循環結束後，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」信息，否則輸出的頂點序列就是一種拓撲序列。

參考資料來源：網路-拓撲排序

參考資料來源：網路-有向圖

『伍』 數據結構拓撲排序序列

對一個有向無環圖簡稱G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u，v>∈E(G)，則u在線性序列中出現在v之前。通叢友常，這樣的線性序列稱為滿足拓撲次序的序列，簡稱野友拓撲序列。

由拓撲序列的生成方法的出圖中三種不同拓撲排序的序列：第一種：c1、c2、c4、c3、c5、c6，第二種：c1、c2、c4、c3、c6、c5，第三種：c1、c3、c2、c4、c5、c6。

循環結束後，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」信息，否則輸出的頂點序列就是一種拓撲序列。

參考資料來源：網路-拓撲排序

『陸』 數據結構拓撲排序序列

拓撲排序序列有6種。先找到第一個沒有被指的，就是C1，加入序列。然後擦掉跟C1有關的邊，此時C2和C3都滿足沒有被指，選一個，比如選C2，加入序列，擦掉和C2有關的邊，這個時候可以選C3,C4,C5或C6，如此而已。