树与图的广度优先搜索

贡献者：有机物

预备知识　广度优先搜索（BFS）

　　树与图的广度优先遍历的大致思路和广度优先搜索（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;
}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。