算法刷题笔记 图中点的层次（树的广度优先搜索，详细注释的C++实现）

题目描述

• 给定一个n个点m条边的有向图，图中可能存在重边和自环。
• 所有边的长度都是1，点的编号为1∼n。
• 请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出−1。

输入格式

• 第一行包含两个整数n和m。
• 接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式

• 输出一个整数，表示1号点到n号点的最短距离。

数据范围

• 1 ≤ n,m ≤ 10^5

基本思路

• 本题仍然是一道树的广度优先搜索的模板题，遵循广度优先搜索的一般模板。总体难度较低。
• 以向量数组作为邻接表存储图的边，是一种非常常用的做法。

实现代码

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

// 输入的点的个数和边的条数
int n, m;
// 存储有向图的邻接表
const int N = 100010;
vector<int> adjacent_table[N];
// 存储每个结点是否被搜索到过
bool flag[N];
// 存储每个结点离起点的最短距离
int distances[N];

// 基于广度优先搜索算法计算点p1到点p2的最短距离
int shortest_path_length(int p1, int p2)
{
    // 特殊情况：p1和p2是同一个点，则直接返回0即可
    if(p1 == p2) return 0;
    
    // 构建一个队列
    queue<int> unvisited;
    // 将起点p1放入队列中
    unvisited.push(p1);
    // 将起点设置为已经被搜索到过
    flag[p1] = true;
    // 每次从队列中取出队首元素进行访问
    while(unvisited.empty() == false)
    {
        // 将队首元素出队
        int current = unvisited.front();
        unvisited.pop();
        //逐一找出队首元素还没有被找到过的邻居
        for(int neighbor : adjacent_table[current])
        {
            if(flag[neighbor] == false)
            {
                // 将邻居元素设置为已经找到过
                flag[neighbor] = true;
                // 设置该结点的距离
                distances[neighbor] = distances[current] + 1;
                // 特殊情况：当前的邻居刚好是终点p2，则直接返回结果即可
                if(neighbor == p2) return distances[neighbor];
                // 将该结点入队
                unvisited.push(neighbor);
            }
        }
    }
    // 如果队列为空仍然没有找到编号为p2的结点，则返回-1
    return -1;
}

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++ i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        adjacent_table[a].push_back(b);
    }
    printf("%d", shortest_path_length(1, n));
    return 0;
}