二Day1A - Breadth First Search

• 题目正文
• • 代码
• 总结

题目正文

Write a program which reads an directed graph G=(V,E), and finds the shortest distance from vertex 1 to each vertex (the number of edges in the shortest path). Vertices are identified by IDs 1,2,…n.

Input
In the first line, an integer n denoting the number of vertices, is given. In the next n lines, adjacent lists of vertex u are given in the following format:

u k v1 v2 … vk

u is ID of the vertex and k denotes its degree.vi are IDs of vertices adjacent to u.

Constraints
1≤n≤100
Output
For each vertex u, print id and d in a line. id is ID of vertex u and d is the distance from vertex 1 to vertex u. If there are no path from vertex 1 to vertex u, print -1 as the shortest distance. Print in order of IDs.

Sample Input 1
4
1 2 2 4
2 1 4
3 0
4 1 3
Sample Output 1
1 0
2 1
3 2
4 1

代码

代码：

//1.定义最大值maxn,定义一个无穷大的数0x3f3f,设置一个二维数组，一个一维数组
//2.bfs()函数中传入参数，定义一个队列，s进队列，循环，一维数组的每个值设置为无穷大
//3.while循环q队列不为空，定义队首指针，并出队列，for循环，遍历相邻顶点
//4.如果邻接矩阵的顶点为零，跳出，如果顶点不为无穷跳出，否则，相邻顶点加1，进队列
//5.循环输出，是否为inf，是，输出-1，否则输出该顶点的数
//6.主函数里，，定义N，输入n,两层循环二维数组为0，两层循环输入u,k,u--
//7.第二层循环输入v,v--;e[u][v]=1,调用bfs()
#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=50;
const int inf=0x3f3f;
int d[maxn],e[maxn][maxn];
int n;
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    for(int i=0;i<n;i++)
        d[i]=inf;
    d[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int v=0;v<n;v++)
        {
            if(e[u][v]==0)continue;
            if(d[v]!=inf)continue;
            d[v]=d[u]+1;
            q.push(v);
        }
    }
    for(int i=0;i<n;i++)
    {
        cout<<(i+1)<<" "<<((d[i]==inf)?(-1):d[i])<<endl;
    }
}
int main()
{
    int u,v,k;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        e[i][j]=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&u,&k);
        u--;
        for(int j=0;j<k;j++)
        {
            scanf("%d",&v);
            v--;
            e[u][v]=1;
        }
    }
    bfs(0);
    return 0;
}

总结

bfs()的运用