滴水逆向联盟

标题: VC++2012编程演练数据结构《28》拓扑排序算法 [打印本页]

---

作者: 大灰狼    时间: 2014-8-19 08:55
标题: VC++2012编程演练数据结构《28》拓扑排序算法
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。
什么是拓扑序列
　　通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：
　　若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
　　设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。
　　注意：
　　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
　　②若图中存在有向环，则不可能使顶点满足拓扑次序。
　　③一个DAG的拓扑序列通常表示某种方案切实可行。
一般应用
　　拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。
实现的基本方法
　　拓扑排序方法如下:
　　(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
　　(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

　　(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

打开ＩＤＥ

我们创建一个工程

定义声明如下

[cpp] view plaincopy

• #include "stdafx.h"  
•   
• //拓扑排序  
• #include<iostream>  
• #include<iomanip>  
• #include<stdlib.h>  
• using namespace std;  
• typedef struct  
• {char w1,w2;  
• float w;  
• }RCW;  
• typedef struct  
• {char *data;  
• int *visited;  
• float **edge;  
• int max,size;  
• }Graph;  
• //初始化图  
• void SetGraph(Graph *G,int n)  
• {int i,j;  
• G->data=new char[n];  
• G->visited=new int[n];  
• G->edge=(float **)malloc(n*sizeof(float *));  
• for(i=0;i<n;i++)  
• G->edge=(float *)malloc(n*sizeof(float));  
• for(i=0;i<n;i++) G->visited=0;  
• for(i=0;i<n;i++)  
• for(j=0;j<n;j++) G->edge[j]=0;  
• G->max=n;  
• G->size=0;  
• }  
• //构造图  
• void MakeGraph(Graph *G,RCW r[],int n,int e)  
• {int m=0;  
• while(m<n)  
• {if(G->size==G->max)  
• {cout<<"Graph is full!\n";  
• exit(1);}  
• G->data[G->size]='a'+m;  
• G->size++;m++;}  
• //插入弧  
• for(int p=0;p<e;p++)  
• {int i,j,k;  
• for(k=0;k<n;k++)  
• {if(r[p].w1==G->data[k]) i=k;  
• if(r[p].w2==G->data[k]) j=k;}  
• G->edge[j]=r[p].w;}  
• }  
•   
• typedef struct  
• {int *data;  
• int max,top;  
• }Stack;  
• void TopSort(Graph *G)  
• {int i,j,n,d,count=0,*D;  
• Stack S;  
• if(G->size==0) return;  
• n=G->size;  
• S.data=new int[n];  
• S.max=n;S.top=-1;  
• D=new int[n];  
• for(j=0;j<n;j++)  
• {d=0;  
• for(i=0;i<n;i++)  
• if(G->edge[j]!=0) d++;  
• D[j]=d;  
• if(d==0)  
• {if(S.top==S.max-1)  
• {cout<<"Stack is full!\n";exit(1);}  
• S.top++;  
• S.data[S.top]=j;  
• }  
• }  
• while(!(S.top==-1))  
• {if(S.top==-1)  
• {cout<<"Pop an empty stack!\n";exit(1);}  
• S.top--;  
• i=S.data[S.top+1];  
• cout<<G->data<<' ';  
• count++;  
• for(j=0;j<n;j++)  
• if(G->edge[j]!=0)  
• {D[j]--;  
• if(D[j]==0)  
• {if(S.top==S.max-1)  
• {cout<<"Stack is full!\n";exit(1);}  
• S.top++;  
• S.data[S.top]=j;  
• }}}  
• if(count<n)  
• cout<<"\nThere is a cycle.";  
• free(D);  
• free(S.data);  
• }  
  

调用如下

[cpp] view plaincopy

• void main()  
• {cout<<"运行结果:\n";  
• Graph G;int n=6,e=8;//n为顶点数,e为边数  
• RCW rcw[8]={{'a','b',1},{'a','d',1},{'a','e',1},{'b','f',1},  
• {'c','b',1},{'c','f',1},{'e','d',1},{'e','f',1}};  
• SetGraph(&G,n);  
• MakeGraph(&G,rcw,n,e);  
• TopSort(&G);  
• free(G.data);//释放空间  
• free(G.visited);  
• for(int i=0;i<G.max;i++) free(G.edge);  
• free(G.edge);  
• cin.get();  
• }  
  

效果如下

---

欢迎光临 滴水逆向联盟 (http://dtdebug.com/)

Powered by Discuz! X3.2