算法解析
为什么我觉得宽搜比深搜好理解多了,宽搜无非多了一个队列,深搜集合了递归,回溯,剪枝…枯了
宽搜里的队列就相当于jvm中的程序计数器,通过不断改变程序计数器的值,来维持程序的运行
队列也是一样的,就是不断地加进去,吐出来,吐没了就停止运行,输出结果
Java代码
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
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[] d = new int[N]; //储存每个节点距离起点的距离
static Queue<Integer> q = new LinkedList<>();
static boolean[] st = new boolean[N];
static int idx,n;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n = in.nextInt();
int m = in.nextInt();
for(int i = 0; i < N; i ++)
{
h[i] = -1;
d[i] = -1;
}
for(int i = 0; i < m; i ++)
{
int a = in.nextInt();
int b = in.nextInt();
add(a,b);
}
System.out.print(bfs(1)); //求的是1-n的最短距离,从1开始搜就可以了
}
private static void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
private static int bfs(int u)
{
q.offer(u);
d[1] = 0; //自己距离自己为0,在这里的作用相当于表示走过了
while(q.size() != 0)
{
int t = q.poll();
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i]; //j相当于当前节点的子节点,因为当前节点会不满足条件直接跳出循环
if(d[j] == -1)
{
q.offer(j);
d[j] = d[t] + 1;
}
}
}
return d[n];
}
}
确实,递归刚开始是真的绕