算法分析
(bfs)
- 1、通过队列实现
bfs
,从原点出发,往指向的点进行枚举,并且相继进栈 - 2、队列中元素出队列时,枚举下一层
- 3、数组
d[]
记录1
到i
最短距离时的值,若值为-1
表示没有遍历过该点
注意:边权都是1
才能使用bfs
搜最短路
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx = 0;
static int n;
static int m;
static int[] d = new int[N];//记录1到i最短距离时的值,若值为-1表示没有遍历过该点
public static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static int bfs()
{
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
d[1] = 0;
while(!queue.isEmpty())
{
int t = queue.poll();
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
queue.add(j);
}
}
}
return d[n];
}
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
Arrays.fill(d, -1);
for(int i = 0;i < m;i++)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
add(a,b);
}
System.out.println(bfs());
}
}
算法分析里面好像把队列错写成了栈
谢谢提醒,已修改