算法之拓撲排序

拓撲排序

概念：

• 拓撲排序是對有向無圈圖的頂點的一種排序。排序不必是唯一的，任何合理的排序都是可以的。
• 具體做法是：先找出任意一個沒有入邊的頂點v(就是沒有其他頂點指向的頂點)，將頂點v放入隊列，然后將頂點v和它鄰接的邊從圖中刪除(其實就是將頂點v指向的頂點的入邊數都-1，這樣就可以代表刪除邊了)，然后用數組topnum來記錄該頂點的排序位置。然后重復上述操作。頂點v的入度(indegree)為邊(u,v)的條數。并用indegree數組來存儲每個頂點的入度值。如果不存在入度為0的頂點，則該圖是個有圈圖。

代碼：

struct listnode{int data;listnode* next;
};class graph{
public:graph(int n){vnum=n;an=new listnode[n+1];indegree=(int*) malloc(sizeof(int)*(n+1));for(int i=0;i<n+1;i++){an[i].data=0;an[i].next= nullptr;indegree[i]=0;}}listnode* createNode(int data){auto p=new listnode;p->data=data;p->next= nullptr;return p;};void insert(int v,int data){auto add= createNode(data);if(an[v].next== nullptr){an[v].next=add;} else{listnode* p=an[v].next;while (p->next!= nullptr){p=p->next;}p->next=add;}indegree[data]++;}int findedgenull(){for(int i=1;i<=vnum;i++){if(indegree[i]==0){return i;}}return 0;}//拓撲排序void topsort(){queue<int>q;int v=findedgenull();if(v==0){cout<<"該圖含有圈"<<endl;return;}else{q.push(v);if(q.empty()){cout<<"該圖含有圈"<<endl;return;}while (!q.empty()){int w=q.front();cout<<w<<" ";q.pop();listnode* p=an[w].next;while (p!= nullptr){if(--indegree[p->data]==0){q.push(p->data);}p=p->next;}}cout<<endl;}}
private:listnode *an;int vnum;int *indegree;
};

尾言

完整版筆記也就是數據結構與算法專欄完整版可到我的博客進行查看，或者在github庫中自取(包含源代碼)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github項目地址：Data-Structure-and-Algorithms