有向圖的拓撲排序演算法

A. 數據結構題。有向圖，給出該圖的一種拓撲排序序列

拓撲排序的方法和步驟：

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

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

答案：1，3，2，4，5

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

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

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

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

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

(2)有向圖的拓撲排序演算法擴展閱讀：

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

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

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

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

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

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

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

C. n 個頂點的有向圖用鄰接矩陣 array 表示，下面是其拓撲排序演算法，試補充完整。

（1） 0
（2） array[j][i]
（3）0
（4）indegree[i] == 0
（5）vex
（6）array[k][i] == 1
（7）indegree[i] == 0
（8） count < n

D. 數據結構 拓撲排序

【1】拓撲排序
在一個表示工程的有向圖中，有頂點表示活動，用弧表示活動之間的優先關系，這樣的有向圖為頂點表示活動的網，我們稱為AOV網。
AOV網中的弧表示活動之間存在的某種制約關系。
所謂拓撲排序，其實就是對一個有向圖構造拓撲序列的過程。
【2】拓撲排序演算法
對AOV網進行拓撲排序的基本思路：
從AOV網中選擇一個入度為0的頂點輸出；
然後刪除此頂點，並刪除以次頂點為尾的弧；
繼續重復此操作.....
直到輸出全部頂點或AOV網中不存在入度為0的頂點為止。
由於拓撲排序過程中，需要刪除頂點，顯然用鄰接表更加方便。
因此我們需要為AOV網建立一個鄰接表。
另外，考慮到演算法過程中始終需要查找入度為0的頂點？
需要在原頂點表節點結構中，增加一個入度域in，in就是入度數字。

E. 數據結構課設 題目：拓撲排序演算法

//首先是用鄰接表表視圖,下面是鄰接表的數據結構定義
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;
}

F. 採用鄰接矩陣存儲結構對有向圖進行拓撲排序的演算法

lint topsort( ALGraph *G) /*拓撲排序*/
{ int i,j,k,top =-1;
EdgeNode *ptr;
for(i=0;i<G->n;i++) /*入度為0入棧*/
{ if(G->adjlist[i].indegree==0)
{ G->adjlist[i].indegree=top;
top=i; }
}
{if(top==-1) return -1; /*網中有迴路*/
j=top;
for(i=0;i<G->n;i++)
{ if(top==-1) return -1;/*AOV網中有迴路*/
j=top;
top=G->adjlist[top].indegree; /*從棧中退出一個入度為0的頂點並輸出*/
printf("->%s",G->adjlist[j].vertex);
ptr=G->adjlist[j].firstedge;
{ k=ptr->adjvex;
G->adjlist[k].indegree--; /*修改其他頂點的入度*/
if(G->adjlist[k].indegree==0) /*為0入棧*/
while(ptr!=NULL)
{
G->adjlist[k].indegree=top;
top=k;
}
ptr=ptr->next;
}
}
}

G. 任意給定一個有向圖，設計一個演算法，對它進行拓撲排序(C++實現)

LS的方法可行，但是比較麻煩，我來說一種特別簡單的方法！

我們for每個點，每次碰到一個未處理過的點就 處理（深搜） 這個點，並 處理（深搜） 這個點連向的所有點，處理完每個點連向的所有點後，在堆棧中加入這個點。

差不多就是這樣：

dfs(點h)
{
visit[h]=true
for(所有h連向的點)
if(!visit[h連向的點])
dfs(h連向的點)
stack[++top]=h
}

for(所有點)
if(!visit[這個點])
dfs(這個點)

然後按棧輸出即可，這個一定是對的，因為我們每次把這個點加入棧之前都已經把這個點連向的點加入棧了，所以滿足拓撲序！

H. 數據結構拓撲排序序列

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

I. 數據結構中 關於圖拓撲排序演算法 有個地方不太明白 希望能得到解答

我知道你哪裡不明白了，你沒看見上面的for循環，1，如果不為0，則不執行if了，但執行for循環。2，執行for循環的目的就是把所有的入度減1，減為0的入棧。