数据结构实验之图论五：从起始点到目标点的最短步数（BFS）

分析：有向图里面找最短路径，原理就是每一步都走距离自己最近的路， 一旦发现走一步可以到，那么这个一定是最短的。

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;
struct node
{
    int step;
    int data;
}l,w;
int vis[1002];
int gra[1002][1002];
int n, m, u, v;
void bfs(int s)
{
    vis[s] = 1;
    w.data = s;
    w.step = 0;
    struct node q[100000];
    int in = 0, out = 0;
    q[in  ] = w;
    while(in > out)
    {
        w = q[out   ];
        if(w.data == 1){
            printf("%dn",w.step);
            return ;
        }
        for(int i = 1; i <= n; i   ){
            if(!vis[i] && gra[w.data][i]){
                l.data = i;
                l.step = w.step   1;
                q[in  ] = l;
            }
        }
    }
    printf("NOn");
}
int main()
{

    while(~scanf("%d%d", &n, &m))
    {
        memset(gra, 0, sizeof(gra));
        memset(vis, 0, sizeof(vis));
        while(m--)
        {
            scanf("%d %d", &u, &v);
            gra[u][v] = 1;
        }
        bfs(n);
    }
    return 0;
}

原理

0 人点赞