目录
- 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语言全局变量默认为0
void 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;
}
}
