树与图的广度优先搜索

                     

贡献者： 有机物

　　 树与图的广度优先遍历的大致思路和广度优先搜索（BFS）差不多，实现 BFS 需要使用一个队列来维护结点，每次先把 $1$ 号结点入队，在依次遍历每一层中的结点，并把这些结点插入到队尾，队头的元素出队，直到队列为空，就遍历完了所有元素。

void bfs()
{
    int hh = 0, tt = -1;
    q[ ++ tt] = 1;
    memset(d, -1, sizeof d);  // 初始化距离，-1 表示没被遍历过
    d[1] = 0;
    
    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)  // 若 j 没被遍历过
            {
                d[j] = d[t] + 1;
                q[ ++ tt] = j;
            }
        }
    }
}

　　 上面的代码完成了图的广度优先遍历，并记录了图中的每个结点的层次（从 $1$ 号结点走到当前结点最少经过几个点）或树中的深度。也可以理解为求出了 $1$ 号结点每个结点的最短距离。

　　 拓扑排序

　　 拓扑序列是指，在一个有向无环图中（在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG 图）），若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x, y)$，$x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的一个拓扑序列。求拓扑序列的过程就被称为拓扑排序。如果一个有向图有环，必定有一条边从后指向前，所以有向有环图显然不会构成拓扑序列，因此有向无环图也被称为拓扑图。

　　 具体的做法是，在读入的过程中并处理每个结点的入度（有多少条边指向自己，边数即为入度），首先将入度为 $0$ 的点入队，入度为 $0$ 说明没有任何一条边指向自己，则当前结点就是拓扑序列中的一点。取出队头并扫描所有出边 $(x, y)$，并删除 $(x, y)$ 这条边，即让 $y$ 号结点的入度减一，为什么删除这条边呢，删除这条边是为了看一下这条边的指向的点（即 $j$ 号点）是不是还有边指向这个结点，如果最后 $j$ 这个结点的入度减到 $0$ 了，说明只有边指向这个结点，即这个结点是拓扑序列中的一点，所有把 $j$ 入队。然后重复上述步骤即可求出拓扑序列，即队列中所有的元素。

　　 如果最后队列中的元素小于点的个数，说明图中不存在拓扑序列，则说明图中有环存在，所以拓扑排序也可以判断图中有没有环。

bool topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ ) // 先将入度为 0 的点入队
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if ( -- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    // 如果队列中的元素小于点的个数，则不存在拓扑序，否则存在
    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);  // 加入有向边 a->b
        d[b] ++ ;   // d[i] 存储点 i 的入度，b 的入度加 1
    }
    
    if (!topsort()) printf("-1\n"); // 图中不存在拓扑排序
    else
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
        printf("\n");
    }
    
    return 0;
}