【32. 图中的层次(图的广度优先遍历)】

简介: 思路- 因为所有的`边长都为1`,所以可以使用`宽度优先搜索`的思想,每当队列pop出一个元素时,将其距离为1的节点都加到队列中(层次遍历思想)- `st[]`标记各个节点有没有走过,`d[]`保存1号节点到各个节点的距离,初始时都为-1。

图中的层次

思路

  • 因为所有的边长都为1,所以可以使用宽度优先搜索的思想,每当队列pop出一个元素时,将其距离为1的节点都加到队列中(层次遍历思想)
  • st[]标记各个节点有没有走过,d[]保存1号节点到各个节点的距离,初始时都为-1。

难点

  • 如何进行层次遍历?

首先需要将图,变成邻接表进行存储。可参照之前写的数组模拟链表,数组模拟链表只是一个头结点,而图的是有n个头结点

1661155578351.png

  • 图中的数组是一个存储头结点,我们给定一个节点1,那么在h[1]指向的这条链表上,都是与节点1相邻的节点(即距离为1)
  • 因此,在pop出一个节点t时,只需使用h[t]指向它的链表,再通过for(int i = h[t]; i != -1; i = ne[i]),就可以遍历一整条链表上的节点。然后在遍历时将其加到队列中,并将其的长度置位h[t]+1即可;
for (int i = h[t]; i != -1; i = ne[i]) // ne[i]上的点都是与i节点距离为1的点
        {
            int j = e[i]; // 向外走一步
            if (d[j] == -1) // 如果j没有被遍历过
            {
                d[j] = d[t] + 1; // 因为路径长度都是1,所以直接在上一步的基础上加上1即可
                q.push(j); // 将j加到队列中
            }
        }

步骤

  1. 1 号节点入队列,dist[1] 的值更新为 0。
  2. 如果队列非空,就取出队头,找到队头节点能到的所有节点。(也就是遍历一条链表上的所有节点,遍历时将这些节点入队)
  3. 如果队头节点能到走到的节点没有标记过,就将节点的dist值更新为队头的d[]值+1,然后入队。
  4. 重复步骤 2,3 直到队列为空。
  5. d[]中就存储了 1 号节点到各个节点的距离了。如果距离是无穷大,则不能到达,输出 -1,如果距离不是无穷大,则能到达,输出距离。

1661155603970.png

注意

  • 边权都是1才能使用bfs搜索最短路径
  • 因为计算机一次性只能处理一个,但是最短路径要求层次遍历,也就是一次性处理多个。此时需要用到队列,来存储这些层次节点(例如上述图中从1号节点,往下走一层,此时走过的点有2, 3,4,这些都是与1号节点距离为1,所以依次将他们入队,距离设置为1.然后再反复运行,直到队列为空)

对于重边和自环解决办法

  • 在一开始add时,会把重边和自环add进去,但是后面访问的时候,设置了一个用来判断是否被访问过的数组st[]来记录图中每个点是否被访问过的

所以这样抵消了重边和自环的影响,也即不会多次访问同一个点。

题目

1661155629120.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 100010;

int h[N],ne[N], e[N], idx;//邻接表数据结构
int d[N];//存储距离
int st[N];//标记点是否走到过
int n, m;

void add(int a, int b)//邻接表存储图
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs()
{
    memset(d, -1, sizeof(d));//初始都没有走到过,距离无穷大
    d[1] = 0;//从1号节点开始,距离为0
    queue<int> q;//队列
    q.push(1);//1号节点入队列
    st[1] = 1;//1到1的距离为0,已经求出
    
    while(q.size())//对列非空,就一直往后搜索
    {
        int t = q.front();//队头出队,找该点能到的点
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点,i为节点索引
        {
            int j = e[i];//通过索引i得到t能到的节点编号
            if(!st[j])//如果没有遍历过
            {
                d[j] = d[t] + 1;//距离为t号节点的距离+1
                q.push(j);//节点入队
                st[j] = 1;//入队后标记,已经遍历过了
            }
        }
    }
    return d[n];
}

int main()
{
    cin >> n >>m;
    memset(h, -1, sizeof h);//初始化,所有节点没有后继,后继都是-1
    for(int i = 0; i < m; i++)//读入所有边
    {
        int a, b;
        cin >> a >> b;
        add(a, b);//加入邻接表
    }
   cout <<  bfs();//广度优先遍历

    
    return 0;
}

目录
相关文章
|
7月前
|
存储 算法
图的深度优先算法
图的深度优先算法
50 0
|
7月前
|
NoSQL 容器 消息中间件
图、图的遍历及图的拓扑排序
图、图的遍历及图的拓扑排序
|
算法 测试技术 C++
C++算法:图中的最短环
C++算法:图中的最短环
图的基本术语,邻接矩阵、邻接表表示方法
图的基本术语,邻接矩阵、邻接表表示方法
L2-023 图着色问题 (25 分)(图的遍历)
L2-023 图着色问题 (25 分)(图的遍历)
76 0
|
存储 算法 搜索推荐
C++实现图 - 05 拓扑排序
今天来讲另一个非常重要的知识点 —— 拓扑排序。咋一看好像是一个排序算法,然而它和排序扯不上半点关系,它可以用于判断我们的图中是否存在有向环。
650 0
C++实现图 - 05 拓扑排序
|
算法
树与图的广度优先遍历
复习acwing算法基础课的内容,本篇为讲解基础算法:树与图的广度优先遍历,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
106 0
树与图的广度优先遍历
L2-023 图着色问题 (25 分)(图论)
L2-023 图着色问题 (25 分)(图论)
391 0