拓扑序列

关于拓扑排序有几点：

1.拓扑序列中，每条有向边都是从序列中前面的顶点指向后面的顶点。

2.有向无环图(DAG)一定有拓扑序列。存在环的图一定没有拓扑序列，因为环必定有从后面的点指向前面的点的边。

3.一个有向无环图一定至少有一个入度为0的点。

4.拓扑排序有多种可能的序列，因为图中可能存在多个入度为零的顶点，而这些顶点可以以任意顺序加入拓扑序列。

如何求拓扑排序？(刚死去的数据结构知识来攻击我了hh

下面这个视频讲了求拓扑排序的方法，推荐看

【数据结构 图 拓扑排序】

求拓扑排序的步骤就是：找到入度为0的顶点，删掉由该顶点指出的所有边，之后，在剩余的顶点中再次找到入度为0的顶点......重复该操作。

而我们代码实现就是，用队列模拟这个过程。

代码如下 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];//d数组此时表示的是每个顶点的入度
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool topsort()
{
    int hh=0,tt=-1;//表示队头 队尾的指针 tt初始化为-1 队列中的元素下标从0开始

    for(int i=1;i<=n;i++)//顶点用1~n表示
    {
        if(!d[i])q[++tt]=i;//入度为0就入队  
        //++tt tt始终表示的是当前队列的最后一个元素
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])//遍历邻接顶点
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)q[++tt]=j;//删除顶点之后，若有顶点由此入度变为0，入队
        }
    }
    return tt==n-1;//当队列尾部的计数与顶点数相同时说明找到了一个拓扑排序

}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);//初始化邻接表的顶点集

    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        d[y]++;//边由x指向y，y的入度要++
    }

    if(topsort())
    {
//数组模拟队列只是定义了队头队尾指针，通过这两个指针的移动来划定队列范围，然鹅在q数组中其实是包含所有插入的元素的。刚好我们元素插入的顺序就是拓扑序列
        for(int i=0;i<n;i++)
        {
            cout<<q[i]<<" ";
        }
    }
    else cout<<"-1"<<endl;
    return 0;
}

---

因为思路比较好理解，之前也写过几个bfs的题目，这里解释就比较少，之后看有需要补充的会再回来改一下。这次先写到这里~

有问题欢迎指出！一起加油！！