树与图的广度优先搜索

                     

贡献者: 有机物

预备知识 广度优先搜索(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;
}

                     

© 小时科技 保留一切权利