1、實驗目的：
（1）熟練掌握圖的基本存放裝置方法；
（2）熟練掌握圖的深度優先和廣度優先搜索方法；
（3）掌握AOV網和拓撲排序演算法；
（4）掌握AOE網和關鍵路徑。
2、實驗內容：拓撲排序。
任意給定一個有向圖，設計一個演算法，對它進行拓撲排序。拓撲排序演算法思想：a.在有向圖中任選一個沒有前趨的頂點輸出；b.從圖中刪除該頂點和所有以它為尾的弧；c.重複上述a、b，直到全部頂點都已輸出，此時，頂點輸出序列即為一個拓朴有序序列；或者直到圖中沒有無前趨的頂點為止，此情形表明有向圖中存在環。
3、實驗說明：
拓撲排序演算法偽代碼如下：
1.棧S初始化；累加器count初始化；
2.掃描頂點表，將沒有前驅（即入度為0）的頂點壓棧；
3.當棧S非空時迴圈
3.1 vj=退出棧頂元素；輸出vj；累加器加1；
3.2 將頂點vj的各個鄰接點的入度減1；
3.3 將新的入度為0的頂點入棧；
4. if (count<vertexNum) 輸出有回路資訊
4.來源程式代碼：
#include<iostream>
using namespace std;
#define maxsize 50
struct node
{
int adjvex;
node * next;
};
struct graph
{
int vexter;
int in;
node * firstedge;
};
typedef struct
{
int *base;
int *top;
int stacksize;
}sqstack;
void initstack(sqstack &S)
{
S.base=(int *)malloc(sizeof(int));
S.top=S.base;
S.stacksize=maxsize+1;
}
void createadlist(graph inDegree[],int n,int e)//創建鄰接鏈表
{
int i,k,j;
node * q;
for(i=1;i<=n;i++)
{
inDegree[i].vexter=i;
inDegree[i].in=0;
inDegree[i].firstedge=Null;
}
for(k=1;k<=e;k++)
{
cout<<"依次輸入每一條邊：\n";
cout<<"從";
cin>>i;
cout<<"鄰接到";
cin>>j;
cout<<'\n';
inDegree[j].in++;
q=(node *)malloc(sizeof(struct node));
q->adjvex=j;
q->next=inDegree[i].firstedge;
inDegree[i].firstedge=q;
}
}
void TopoSort(graph inDegree[],int n)
{
int i,v,count=0;
sqstack S;
node * p;
initstack(S);
for(i=1;i<=n;i++)
if(inDegree[i].in==0)
*S.top++=i;
while(S.top!=S.base)
{
v=*--S.top;
cout<<v<<"\t";
count++;
p=inDegree[v].firstedge;
while(p!=Null)
{
inDegree[p->adjvex].in--;
if(inDegree[p->adjvex].in==0)
*S.top++=p->adjvex;
p=p->next;
}
}
cout<<endl;
if(count<n) cout<<"有回路"<<endl;
else cout<<"無回路"<<endl;
}
void main()
{
graph inDegree[maxsize];
int v,e;
cout<<"該AOV網的頂點數：";
cin>>v;
cout<<"該AOV網的邊條數：";
cin>>e;
createadlist(inDegree,v,e);
cout<<"拓撲排序序列為："<<endl;
TopoSort(inDegree,v);
}
全站熱搜
留言列表
