DAG圖也成為有向無環(huán)圖，拓?fù)渑判虻臅r間復(fù)雜度為O(V+E)，其中V、E分別為頂點和邊的個數(shù)。

#include <iostream> using namespace std; #define Maxsize 100 typedef char VertexType; typedef int EdgeType;typedef struct ArcNode{ //存儲邊 int adjvex; //該弧所指向的頂點 struct ArcNode *nextarc; //指向下一條弧//InfoType info; //網(wǎng)的邊權(quán)值 }ArcNode; typedef struct VNode{VertexType data; //頂點信息int count; //新增部分，統(tǒng)計當(dāng)前入度 ArcNode *firstarc; //指向第一條邊的指針 }VNode; typedef struct{VNode adjlist[Maxsize];int vexnum,arcnum; }AGraph; bool TopSort(AGraph *G){int i,j,n=0;Stack S;InitStack(S); //初始化棧ArcNode *p;for(i=0;i<G->vexnum;i++)if(G->adjlist[i].count==0)Push(&S,i); //入度為0的頂點進(jìn)棧 while(!IsEmpty(S)){Pop(&S,i);cout<<i<<endl; //輸出頂點i n++; //統(tǒng)計已輸出頂點個數(shù)p=G->adjlist[i].firstarc;while(p!=NULL){j=p->adjvex;G->adjlist[j].count--; //i頂點引出的邊所指向的頂點入度減1if(G->adjlist[j].count==0)Push(&S,j); //入度為0的頂點入棧p=p->nextarc; } }if(n==G->vexnum)return true; //拓?fù)渑判虺晒lsereturn false; //圖有環(huán)路(n<G->vexnum)，拓?fù)渑判蚴? }

?

總結(jié)

以上是生活随笔為你收集整理的DAG图之拓扑排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。