㈠ 求詳解 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)。這個演算法雖然簡單，但是沒有前面一個演算法的效率高。
㈡ 高手解答 全拓撲排序 c語言演算法 或者 演算法思想也行啊
拓撲排序，很多時候，會作為演算法的預處理。
它是針對有向無環圖。
我空間中寫過，比較詳細。
演算法思想：
針對一個有向無環圖，求它的拓撲排序的一個簡單方法：首先找到這個圖中入度為0的頂點。把它放在序列的第一個位置，然後刪除改頂點和它的邊。得到一個新的有向無環圖，在找這個圖中入度為0的頂點。放在序列的下一個位置，然後再刪除改頂點和它的邊。。。，這個步驟重復直到圖中所有的頂點都在序列中。
詳細請看，有程序代碼和相應的圖片說明。
http://hi..com/huifeng00/blog/item/667348af89c42e044b36d6a6.html
㈢ 數據結構，這個帶權圖的拓撲排序什麼思路
由AOV網構造拓撲序列的拓撲排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。
(1) 選擇一個入度為0的頂點並輸出之；
(2) 從網中刪除此頂點及所有出邊。
就是輸出所有箭頭都向外指的節點，然後刪除與該節點相連的邊，一直循環直到節點都輸出或不能夠找到這樣的節點。
顯然，拓撲排序不一定唯一。
題目的一種拓撲排序：
S,G,D,A,B,H,E,I,F,C,T
㈣ 數據結構拓撲排序序列
拓撲排序序列有6種。先找到第一個沒有被指的，就是C1，加入序列。然後擦掉跟C1有關的邊，此時C2和C3都滿足沒有被指，選一個，比如選C2，加入序列，擦掉和C2有關的邊，這個時候可以選C3,C4,C5或C6，如此而已。
㈤ 請解釋下拓撲排序的定義。。和實現方法。。別復制百度百科。。
拓撲排序 所謂拓撲序列，就是有向圖的最長路徑問題，如果圖中存在環，則最長路徑是無法求得的，所以有拓撲序列的有向圖不可以存在環。具體定義如下：
給出有向圖G=（V，E），若結點的線形序列V1,V2,...Vn滿足條件：對於i,j(1≤j<i≤n)，Vi和Vj之間沒有邊。求線形序列V1,V2,...Vn的過程就稱為拓撲排序，這個線形序列就稱為拓撲序列。
【拓撲排序主要思想】
有向圖可以拓撲排序的條件是：圖中沒有環。
具體方法：
⑴ 從圖中選擇一個入度為0的點加入拓撲序列。
⑵ 從圖中刪除該結點以及它的所有出邊（即與之相鄰點入度減1）。
反復執行這兩個步驟，直到所有結點都已經進入拓撲序列。
【實例：士兵排隊問題】
有n個士兵(1≤n≤26)，依次編號為A,B,C,...，隊列訓練時，指揮官要把一些士兵從高到矮排成一行。但現在指揮官不能直接獲得每個人的身高信息，只能獲得逗p1比p2高地這樣的比較結果，記作（p1>p2）。例如A>B，B>D，F>D，對應的排隊方案有三個：AFBD，FABD，ABFD
【輸入】
k行，每行a b，表示a>b
【輸出】
一個可行的排隊方案
【輸入樣例】
A B
B D
F D
【輸出樣例】
ABFD
㈥ 數據結構課設 題目：拓撲排序演算法
//首先是用鄰接表表視圖,下面是鄰接表的數據結構定義
const int MaxVertexNum = {圖的最大頂點數，要大於等於具體圖的頂點數n};
const int MaxEdgetNum = {圖的最大邊數，要大於等於具體圖的邊數e};
typedef VertexType vexlist[MaxVertexNum]; //定義vexlist為存儲頂點信息的數組類型
struct edgenode //定義鄰接表中的邊結點類型
{
int adjvex; //鄰接點域
int weight; //權值域
edgenode* next;//指向下一個邊結點的鏈域
};
typedef edgenode* adjlist[MaxVertexNum]; //定義adjlist為存儲n個表頭指針的數組類型
//通過從鍵盤上輸入的n個頂點信息和e條有向邊信息建立頂點數組GV和鄰接表GL
void Create2(vexlist GV, adjlist GL, int n, int e)
{
int i,j,k;
//建立頂點數組
cout<<"輸入"<<n<<"個頂點的值："<<endl;
four(i = 0; i<n; i++)
cin>>GV[i];
//初始化鄰接表
for(i=0; i<n; i++)
GL[i] = NULL;
//建立鄰接表
cout<<"輸入"<<e<<"條邊："<<endl;
for(k=1; k<=e; k++)
{
//輸入一條邊<i,j>
cin>>i>>j;
//分配新結點
edgenode* p = new edgenode;
//將j值賦給新結點的鄰接點域
p->adjvex = j;
//將新結點插入到鄰接表表頭
p->next = GL[i];
GL[i] = p;
}
}
//對鄰接表GL表示的有n個頂點的有向圖拓撲排序
void TopoSort(adjlist GL, int n)
{
int i,j,k,top,m=0; //m統計拓撲排序中的頂點數
edgenode* p;
//定義存儲圖中每個頂點入度的一維整型數組d
int* d = new int[n];
//初始化數組d中每個元素值為0
for(i=0; i<n; i++)
d[i] = 0;
//利用數組d記錄每個頂點的入度
for(i = 0; i < n; i++)
{
p = GL[i];
while(p != NULL)
{
j = p->adjvex;
d[j]++;
p = p->next;
}
}
//初始化用於鏈接入度為0的棧頂指針top為-1
top = -1;
//建立初始棧
for(i = 0; i < n; i++)
if(d[i] == 0)
{
d[i] = top;
top = i;
}
//每循環一次刪除一個頂點及所有出邊
while(top != -1)
{
j = top; //j的值為一個入度為0的頂點序號
top = d[top]; //刪除棧頂元素
cout<<j<<' '; //輸出一個入度為0的頂點
m++; //輸出頂點個數加1
p = GL[j]; //p指向鄰接點表的第一個結點
while(p != NULL)
{
k = p->adjvex;
d[k]--;
if( d[k] == 0) //把入度為0的元素進棧
{
d[k] = top;
top = k;
}
p = p->next;
}
}
cout<<endl;
if(m<n)
cout<<"存在迴路！"<<endl;
delete []d;
}