图中点的层次(BFS解法)

题目链接

1. 少不了的邻接表形式存储树或者图

int h[N], e[N], ne[N], idx;  //数组模拟邻接表

2. 距离数组和队列数组

int d[N], q[N];     // 距离数组,队列数组

3. 插入函数add(int a, int b)---头插法

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

4. 题目对应的BFS函数
   • bfs 是否完成的判断条件 --- 队列是否为空

int bfs()
{
    int hh = 0, tt = 0; //初始化队头和队尾
    q[0] = 1; //第一个元素是起点1
    
    memset(d, -1, sizeof d);
    //初始化距离
    d[1] = 0;
    
    while(hh <= tt)
    {
        int t = q[hh ++];
        
        for(int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[ ++ tt] = j;
            }
        }
    }
    return d[n];
}

示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N]; // 数组模拟队列, 距离数组

void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

int bfs()
{
    int tt = 0, hh = 0;
    memset(d, -1, sizeof d);
    q[0] = 1;
    d[1] = 0;
    
    while(hh <= tt)
    {
        int t = q[hh ++];
        
        // 用相邻的节点扩展队列
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)   
            {
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
    }
    return d[n];
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    
    int a, b;
    for(int i = 0; i < m; i ++)
    {
        cin >> a >> b;
        add(a, b);
    }
    
    cout << bfs() << endl;
    
    return 0;
}