GraphTheory

拓扑排序算法

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

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。其中一个有向无环图可以有一个或多个拓扑排序序列。

拓扑排序实现的方法
  1. 在有向图中选一个没有前驱(入度为0)的顶点并且输出。
  2. 从图中删除该顶点和所有以它为始点的边,即删除所有与它有关的边。
    ( 与这个顶点相连的顶点的入度减一)
  3. 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止。
如图
  • 用一个序列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数组是用来存储各个点的入度。
上一篇 下一篇

猜你喜欢

热点阅读