拓扑排序算法

拓扑排序定义

对一个有向无环图(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数组是用来存储各个点的入度。