知识点概述
- 如果有环的话,那么这个工程将无法完成比如 1->2->3->1 如果从1开始做,那3没完成就不能做1, 而不去做1就无法完成3.
- 方向是表示任务之间的优先级.
如果中间有环,则环上的每个节点入度必定>=1,则不会进入拓扑序列中.
算法步骤
邻接表实现
#include<iostream> #include<stack> using namespace std; const int MaxVnum=100;//顶点数最大值 int indegree[MaxVnum];//入度数组 typedef string VexType;//顶点的数据类型为字符型 typedef struct AdjNode{ //定义邻接点类型 int v; //邻接点下标 struct AdjNode *next; //指向下一个邻接点 }AdjNode; typedef struct VexNode{ //定义顶点类型 VexType data; // VexType为顶点的数据类型，根据需要定义 AdjNode *first; //指向第一个邻接点 }VexNode; typedef struct{//包含邻接表和逆邻接表 VexNode Vex[MaxVnum]; //定义邻接表 VexNode converse_Vex[MaxVnum]; //定义逆邻接表 int vexnum,edgenum; //顶点数，边数 }ALGragh; int locatevex(ALGragh G,VexType x) { for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标 if(x==G.Vex[i].data) return i; return -1;//没找到 } void insertedge(ALGragh &G,int i,int j)//插入一条边 { AdjNode *s1,*s2; s1=new AdjNode;//创建邻接表结点 s1->v=j; s1->next=G.Vex[i].first; G.Vex[i].first=s1; s2=new AdjNode;//创建逆邻接表结点 s2->v=i; s2->next=G.converse_Vex[j].first; G.converse_Vex[j].first=s2; } void printg(ALGragh G)//输出邻接表 { cout<<"----------邻接表如下：----------"<<endl; for(int i=0;i<G.vexnum;i++) { AdjNode *t=G.Vex[i].first; cout<<G.Vex[i].data<<"： "; while(t!=NULL) { cout<<"["<<t->v<<"] "; t=t->next; } cout<<endl; } cout<<"----------逆邻接表如下：----------"<<endl; for(int i=0;i<G.vexnum;i++) { AdjNode *t=G.converse_Vex[i].first; cout<<G.converse_Vex[i].data<<"： "; while(t!=NULL) { cout<<"["<<t->v<<"] "; t=t->next; } cout<<endl; } } void CreateALGraph(ALGragh &G)//创建有向图的邻接表和逆邻接表 { int i,j; VexType u,v; cout<<"请输入顶点数和边数:"<<endl; cin>>G.vexnum>>G.edgenum; cout << "请输入顶点信息:"<<endl; for(i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组 { cin>>G.Vex[i].data; G.converse_Vex[i].data=G.Vex[i].data; G.Vex[i].first=NULL; G.converse_Vex[i].first=NULL; } cout<<"请依次输入每条边的两个顶点u,v"<<endl; while(G.edgenum--) { cin>>u>>v; i=locatevex(G,u);//查找顶点u的存储下标 j=locatevex(G,v);//查找顶点v的存储下标 if(i!=-1&&j!=-1) insertedge(G,i,j); else { cout << "输入顶点信息错！请重新输入！"<<endl; G.edgenum++;//本次输入不算 } } } void FindInDegree(ALGragh G){//求出各顶点的入度,存入数组indegree int i,count; for(int i = 0; i <G.vexnum; i++){ count = 0; AdjNode *p = G.converse_Vex[i].first; while(p){ p = p->next; count++; } indegree[i] = count;//将 入度存入数组 } cout<<"入度数组为:"<<endl; for(int i = 0; i < G.vexnum ;i++){ cout<<indegree[i]<<"\t"; } cout<<endl; } bool TopologicalSort(ALGragh G,int topo[]){ stack<int> s;//因为删除一个顶点后可能会出现多个顶点的 入度为0,但为了保证拓扑序列唯一性,得依赖于栈. FindInDegree(G); for(int i = 0; i < G.vexnum; i++){ if(!indegree[i]){//入度为0的进栈. s.push(i); } } int x,m; m = 0;//控制拓扑序列下标的移动 while(!s.empty()){//将图中的点放入到拓扑序列中 x = s.top(); s.pop(); topo[m] = x; m++; AdjNode *p = G.Vex[x].first;//p指向i的第一个邻接点 while(p){//让x的所有邻接点入度-1 int k = p->v; indegree[k]--; if(!indegree[k]){//入度为0则进栈 s.push(k); } p = p->next; } } if(m<G.vexnum){//判断是否有回路 return false; }else{ return true; } } int main() { ALGragh G; int *topo = new int[G.vexnum];//拓扑数组中存放的是节点的下标。 CreateALGraph(G);//创建有向图的邻接表和逆邻接表. printg(G);//打印邻接表和逆邻接表. if(TopologicalSort(G,topo)){ cout<<"拓扑序列为:"<<endl; for(int i = 0; i < G.vexnum; i++){ int index = topo[i]; cout<<G.Vex[index].data<<"\t"; } }else{ cout<<"该图有环,无拓扑序列!"<<endl; } return 0; } //1 2 //1 3 //3 2 //3 4 //2 6 //2 4 //6 5 //4 5
运行结果:
算法分析
邻接矩阵实现
#include<iostream> #include<stack> #include<string.h> using namespace std; const int maxn = 105; int map[maxn][maxn],indegree[maxn],topo[maxn]; int n,m; stack<int> s; void TopoSort(){//拓扑排序 int cnt = 0; for(int i = 1; i <= n; i++){//入度为0入栈. if(indegree[i]==0){ s.push(i); } } while(!s.empty()){ int u = s.top(); s.pop(); topo[cnt++] = u; for(int j = 1; j <= n; j++){ if(map[u][j]){ if(--indegree[j]==0){ s.push(j); } } } } } int main(){ cin>>n>>m; memset(map,0,sizeof(map)); memset(indegree,0,sizeof(indegree)); for(int i = 1;i<=m; i++){ int u,v; cin>>u>>v; map[u][v] = 1; indegree[v]++; } TopoSort(); for(int i = 0; i < n;i++){ cout<<topo[i]<<"\t"; } cout<<endl; return 0; }
运行结果:
第二种实现较为简洁,在读入边的时候就开始初始化入度数组.刷题常用,但时间复杂度为O(n^2),可以使用链式前向星继续优化,则时间复杂度可变为O(n+e)
