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);

}
創作者介紹

資訊園

shadow 發表在 痞客邦 PIXNET 留言(0) 人氣()