拓扑排序算法
2019-06-15 本文已影响51人
雨落八千里

拓扑排序定义
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。其中一个有向无环图可以有一个或多个拓扑排序序列。
拓扑排序实现的方法
- 在有向图中选一个没有前驱(入度为0)的顶点并且输出。
- 从图中删除该顶点和所有以它为始点的边,即删除所有与它有关的边。
( 与这个顶点相连的顶点的入度减一)- 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止。
如图
![]()
用一个序列M( )存储拓扑排序
图a中入度为0的点有 V1,V6;在(V1,V6)中随便选择一个点,选择 V6 并输出 V6,现在 M ( V6 );
将V6与V4,和V6与V5的边删除,得到图b;图b中入度为0的点只有V1,将 V1 输出,M(V6--->V1) ;
把 V1 与 V4 , V1 与 V3 , V1 与 V2 的边删除,得到图c;图c中入度为0的点有V4,V3,这里选择V4,将V4输出, M (V6--->V1--->V4);
将V4与V5这条边删除,得到图d;图d中入度为0的点只有V3,将V3 输出,M(V6--->V1--->V4--->V3);
将V3与V2,V3与V5 的边删除,得到图e;图e中入度为0的点有V2,V5,这里选择V2,输出V2,M(V6--->V1--->V4--->V3--->V2);
没有与V2相连的边,得到图f;图f中只有一个入度为0的点,输出V5,M(V6--->V1--->V4--->V3--->V2--->V5)。
M序列只是这个图的拓扑序列中的其中一种
度
- 在无向图中,顶点 v 作为边的端点的次数之和为 v 的度数,简称度,记作d(v).
- 在有向图中,称顶点 v 作为边的始点的次数之和为 v 的出度,称顶点 v 作为边的终点的次数之和为 v 的入度;称 顶点 v 作为边的端点的次数之和为 v 的度数,简称度.
#include<bits/stdc++.h>
using namespace std;
int edge[100][100];
int du[100];
int n,m;
int main( )
{
memset(edge,0,sizeof(edge));
memset(du,0,sizeof(du));
cin>>n>>m;
int x,y;
for(int i=1; i<=m; i++)
{
cin>>x>>y;
edge[x][y]=1;
}
for(int i=1; i<=n; i++)
{
int k=0;
for(int j=1; j<=n; j++)
{
if(edge[j][i]==1)//根据入度定义 以顶点 i 为终点的边数有几条,i的入度就是几
{
k++;
}
}
du[i]=k;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<edge[i][j];
}
cout<<endl;
}
cout<<endl;
for(int i=1;i<=n;i++)
{
cout<<du[i]<<" ";
}
cout<<endl;
int cnt=0;
while(1)
{
for(int i=1; i<=n; i++)//重复步骤,直到点全部输出
{
if(du[i]==0)
{
cout<<i<<" ";
cnt++;
du[i]=-1;
for(int j=1; j<=n; j++)
{
if(edge[i][j]==1)
{
du[j]--;
}
}
}
}
if(cnt==n)
{
break;
}
}
cout<<endl;
return 0;
}
- du数组是用来存储各个点的入度。