目录
- bfs dfs
- dfs
- 题目
bfs dfs
树、迷宫是图的特殊形式
迷宫问题常用bfs
BFS DFS算法 可以解决 图论问题，这只是它们的用途之一
bfs = breadth First Search
= 宽度优先搜索算法 = 广度优先搜索
dfs = depth First Search
= 深度优先搜索
bfs = breadth First Search
= 宽度优先搜索算法 = 广度优先搜索
非递归
Dijkstra单源最短路径算法、Prim最小生成树算法 与 宽度优先搜索类似
属于一种盲目搜寻法
dfs = depth First Search
= 深度优先搜索
遍历整张图
https://blog.csdn.net/qq_41816189/article/details/122787939
dfs 深度优先搜索 Depth
bfs 宽度优先搜索 Breadth
非递归：
DFS
1.栈
2 从源节点开始把节点按照深度放入栈，然后弹出
3 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
4 直到栈为空
BFS
1 队列
2 从源节点开始依次按照宽度进队列，然后弹出(头部弹出)
3 每弹出一个节点，就把该节点所有没有进过队列的邻接点放入队列
4 直到队列为空
dfs
https://blog.csdn.net/m0_46549425/article/details/108025133
递归
void dfs(int step){判断边界尝试每一种可能 for(i=1;i<=n;i++){继续下一步 dfs(step+1)}返回
}
详解
输入一个数n，输出n的全排列
把牌放入盒子
for(int i=1;i<=n;i++)a[step]=i;//将i号扑克牌放到第step个盒子中----------------------------------------
当前扑克牌是否被使用
for(int i=1;i<=n;i++){if(book[i]==0){ //说明i号扑克牌还在手里，需要放入step号盒子a[step]=i;//将i号扑克牌放到第step个盒子中book[i]=1;//此时i号扑克牌已经被使用}
}----------------------------------------
盒子标记step
void dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌for(int i=1;i<=n;i++){if(book[i]==0){ //说明i号扑克牌还在手里，需要放入step号盒子a[step]=i;//将i号扑克牌放到第step个盒子中book[i]=1;//此时i号扑克牌已经被使用}}
}----------------------------------------void dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌for(int i=1;i<=n;i++){if(book[i]==0){ //说明i号扑克牌还在手里，需要放入step号盒子a[step]=i;//将i号扑克牌放到第step个盒子中book[i]=1;//此时i号扑克牌已经被使用dfs(step+1);/*注意这里是自己调用自己，表示此时走到了第step+1个盒子面前*/ book[i]=0;/*book[i]=0表示dfs调用结束了，换句话说就是扑克牌已经全部放完了需要按照顺序将扑克牌收回，重新放，也就是前面所说的*/}}
}
for(int i=1;i<=n;i++){if(book[i]==0){ a[step]=i;//将i号扑克牌放到第step个盒子中book[i]=1;//此时i号扑克牌已经被使用dfs(step+1);book[i]=0; // 将扑克牌收回，重新放}
}
该代码
完整代码：
#include<stdio.h>
int a[10],book[10],n;
//这里还有需要注意的地方C语言全局变量默认为0void dfs(int step){ //此时在第step盒子面前，需要往里面放第i张扑克牌int i;if(step==n+1){ //这里说明前面的n个盒子已经放好了，这是dfs结束的标志 for(i=1;i<=n;i++)printf("%d",a[i]);printf("\n");return ;/* 注意这个 return 它的作用不是返回主函数，而是返回上一级的dfs函数例：如果此时是 dfs(5),遇到这个 return 就会回到上一级的 dfs函数 也就是dfs(4),但此时dfs(4)的大部分语句已经执行了，只需要接着执行 book[i]=0然后继续进入for循环进入下一次的 dfs函数，直到结束。 */ }for(int i=1;i<=n;i++){if(book[i]==0){ //说明i号扑克牌还在手里，需要放入step号盒子a[step]=i;//将i号扑克牌放到第step个盒子中book[i]=1;//此时i号扑克牌已经被使用 dfs(step+1);/*注意这里是自己调用自己，表示此时走到了第step+1个盒子面前*/ book[i]=0;/*book[i]=0表示dfs调用结束了，换句话说就是扑克牌已经全部放完了需要按照顺序将扑克牌收回，重新放，也就是前面所说的*/}}return;//这里表示这一级别的dfs函数已经结束了，返回上一级 dfs函数 }
int main(){scanf("%d",&n);dfs(1); //dfs函数的开始 return 0;
}题目
https://leetcode.cn/problems/frog-position-after-t-seconds/description/
bfs
class Node {int id;double probability;public Node(int id, double probability) {this.id = id;this.probability = probability;}
}public class test409 {public static void main(String[] args) {
// int[][] edges = new int[][] {{1, 2}, {1, 3}, {1, 7}, {2, 4}, {2, 6}, {3, 5}};
// int n = 7, t = 2, target = 4;int[][] edges = new int[][] {{2, 1}, {3, 1}, {4, 2}, {5, 3}, {6, 5}, {7, 4},{8,7},{9,7}};int n = 9, t = 1, target = 8;double ans = frogPosition(n, edges, t, target);System.out.println(ans);}public static double frogPosition(int n, int[][] edges, int t, int target) {// map 记录结构HashMap<Integer, List<Integer>> map = new HashMap();for (int[] e : edges) {map.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);map.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);}// 准备 bfs：// 双端队列ArrayDeque<Node> queue = new ArrayDeque<Node>();queue.add(new Node(1, 1));// 访问记录表boolean[] vis = new boolean[n + 1];vis[1] = true;int step = 0;// 开始广度搜索while (queue.size() != 0) {for (int size = queue.size(); size > 0; size--) {Node cur = queue.pollFirst(); // 取队元素// t秒判断if (step == t && cur.id == target) {return cur.probability;}List<Integer> list = map.getOrDefault(cur.id, Collections.emptyList());long length = list.stream().filter(k -> !vis[k]).count(); // 未遍历的节点if (length == 0) {if (cur.id == target) {return cur.probability;}continue;}for (Integer l : list) {if (vis[l]) {continue;}vis[l] = true;queue.add(new Node(l, cur.probability/length));}}step++; // 注意 step++ 的位置if (step > t) break;}return 0;}
}
dfs：
public class test409 {public static void main(String[] args) {int[][] edges = new int[][] {{1, 2}, {1, 3}, {1, 7}, {2, 4}, {2, 6}, {3, 5}};int n = 7, t = 1, target = 7;double ans = frogPosition(n, edges, t, target);System.out.println(ans);}static Map<Integer,List<Integer>> map = new HashMap<>();//dfspublic static double frogPosition(int n, int[][] edges, int t, int target){for (var e : edges) {map.computeIfAbsent(e[0],k->new ArrayList<>()).add(e[1]);map.computeIfAbsent(e[1],k->new ArrayList<>()).add(e[0]);}return dfs(1,-1,t,target, 1);}private static double dfs(int id, int father, int step, int target, double pro) {if (step == 0){if(id == target){return pro;}elsereturn 0;}var nodes = map.getOrDefault(id,new ArrayList<>());var length = nodes.size();if (nodes.contains(father)){length--;}if(length == 0){if(id == target){return pro;}elsereturn 0;}for (var node:nodes){if(node == father){continue;}var ans = dfs(node,id,step-1, target, pro/length);if (ans > 0){return ans;}}return 0;}
}
