广度优先搜索与深度优先搜索
程序员文章站
2022-05-21 15:06:22
...
总结
老规矩–站在巨人的肩膀上前行，看大佬们的经验帖：算法入门–深度优先搜索
总结一下收获
深度优先搜索：
- 从一个顶点开始沿一条路走到底，直到到达终点或者不能走，回溯到上一节点，找到该层的其他节点，继续深搜。有递归和非递归实现。
- 缺点：难以寻找最优解，仅仅能寻找有解的情况。
- 优点：每次只用维护一个节点，内存消耗小。
广度优先搜索：
- 从一个顶点开始到下一层所有的节点都开一条路径，不回溯。一般用队列和while实现。
- 缺点：每一个节点入队，其同层的所有节点都要入队，在树的层次较深且子节点较多时内存消耗太大，故广度优先索搜适用于子节点和树的层次较少的情况。
- 优点：可查找出最短路径
广度优先搜索
基础–队列
c++的queue几个常用用法
1. pop() 队首元素出队
2. push() 压入队尾
3. front() 取队头元素
4. empty() 判断队是否为空
题目
试题 E: 迷宫（2019第十届蓝桥杯大赛软件类省赛 C/C++ 大学 B 组）
本题总分：15 分
【问题描述】
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）
New Online Judge
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填 写多余的内容将无法得分。
- 字典序：下一步的方向顺序确定，用三个数组分别映射下一步行、列的变化和方向字母
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int x,y;
string ans;
}Node;
int a[55][55];
int visited[55][55] = {0};
char dirs[] = {'D','L','R','U'};
int row[] = {1,0,0,-1};
int col[] = {0,-1,1,0};
queue<Node> q;
void bfs(){
Node n;
n.x = 1;
n.y = 1;
q.push(n); //初始化起点
while(!q.empty()){
Node k = q.front();
if(k.x==30 && k.y == 50){ //判断队首是否已经到达终点,此时一定是最短路径
cout << k.ans << endl;
return;
}
for(int i=0;i<4;i++){
Node t;
t.x = k.x+row[i];
t.y = k.y+col[i];
t.ans = k.ans + dirs[i];
if((t.x <= 30 && t.x >= 1) && (t.y <= 50 && t.y>=1) && a[t.x][t.y] == '0' && visited[t.x][t.y] == 0){
q.push(t); //插入队尾
visited[t.x][t.y] = 1;
}
}
q.pop(); //弹出队首，即已经使用过的节点k
}
}
int main(){
string s;
for(int i=1;i<=30;i++){
cin >> s;
for(int j=1;j<=50;j++){
a[i][j] = s[j-1];
}
}
bfs();
// cout << "DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR";
return 0;
}
答案:
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
102. 二叉树的层序遍历（Leetcode）
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
参照官方题解写的
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > res;
if(!root){
return res;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int LevelNode = q.size(); //新的一层
res.push_back(vector<int> ());
for(int i=1;i<=LevelNode;i++){
TreeNode *tmp = q.front();
q.pop();
res.back().push_back(tmp->val); //存进的为值
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
}
return res;
}
};
深度优先搜索
核心代码
/**
* DFS核心伪代码
* 前置条件是visit数组全部设置成false
* @param n 当前开始搜索的节点
* @param d 当前到达的深度
* @return 是否有解
*/
bool visited[N] = false;
void dfs(int d,Node node){
if(isEnd(d,node)){ // 一旦到达终点，通知上一层有解
return true;
}
for(Node nextnode in node){ // 回溯时，访问n的相邻节点
if(!visited[nextnode]){ //该节点
visited[nextnode] = true; //在该节点下搜索时该节点不能再次出现
if(dfs(d+1,nextnode)){ // 如果该条路径可以到达终点
//进行一些操作，如记录深度等
return true; //该路径有解，则层层向上通知有解
}
visited[node] = false; //该节点可能会再出现在其他路径中，设置为可访问。
}
}
return false; //本次搜索无解
}
皇后问题
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
C++实现
int a[9];
int ans = 0;
bool check(int x,int y){
for(int i=1;i<x;i++){
if((a[i]+i == x+y) || (a[i]-i == y-x) || (a[i] == y))
return false;
}
return true;
}
bool dfs(int row,int n){
if(row==n+1){ // 最后一行，即第n行都已经放好皇后了，即到达终点了
ans++;
return true;
}
for(int i=1;i<=n;i++){ //确定第row行应该在那一列放皇后
if(check(row,i)){ //如果满足条件
a[row] = i;
dfs(row+1,n); //回溯找其他的解
}
}
}
int main(){
int n;
cin >> n;
dfs(1,n);
cout << ans;
return 0;
}
python实现
global n
global cnt
global a
def check(x,y):
for i in range(1,x): # 之前放过的行的位置和将要放的位置检测
if a[i]+i == x+y:
return False
if i-a[i] == x-y:
return False
if a[i] == y:
return False
return True
def dfs(row): #搜索
if row == n+1:
global cnt #注意此处一定要声明清楚是global的，不然会被当成内部变量而报错
cnt += 1
print(a[1::])
return
for i in range(1,n+1):
if check(row,i): # 第row 行 第i列
a[row] = i # a[i] 表示第i行应该放在哪一个位置
dfs(row+1) # 回溯，下方其他的解
# a[row] = 0 #不影响
if __name__ == '__main__':
n = int(input("n: "))
a = [0 for f in range(n+1)]
cnt = 0
dfs(1) #从1开始，很多循环直接从1开始，但是从a中取数时，列表还是从0开始的
print("总共的解法有：{}".format(cnt))
2N皇后问题
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
用Python实现：
n = int(input())
grid = [[] for _ in range(n)]
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for k in range(n):
line = input().split()
for j in range(n):
grid[k].append(int(line[j]))
cnt = 0
def check(row, col, maze): # 检查是否可以放皇后
if grid[row][col] == 0:
return False
for i in range(row):
if maze[i] + i == col + row or maze[i] - i == col - row or col == maze[i]:
return False
else:
return True
def queenblack(n, grid, row) :
if row == n:
queenWhite(a,grid,0,n)
return
for i in range(n):
if check(row,i,a):
a[row] = i
queenblack(n, grid, row+1)
def queenWhite(a,grid,row,n):
if row == n:
global cnt
cnt += 1
return
for i in range(n):
if a[row] != i and check(row,i,b):
b[row] = i
queenWhite(a,grid,row+1,n)
queenblack(n, grid, 0)
print(cnt)
危险系数
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
输入
输入数据第一行包含2个整数n(2 < = n < = 1000), m(0 < = m < = 2000),分别代表站点数，通道数；
接下来m行，每行两个整数 u,v (1 < = u, v < = n; u != v)代表一条通道；
最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。
输出
一个整数，如果询问的两点不连通则输出-1.
样例输入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
样例输出
2
用C++实现
#include<bits/stdc++.h>
using namespace std;
int n, m,u,v,t=0,k=-1;//t记录到达终点路径条数，k表示关键点
vector<int> g[1000];
int vis[1000],vts[1000];//vis判断是否访问，vts记录所有路径到达终点时每个点的访问次数
void dfs(int x)
{
if (x == v) //到达终点
{
for (int i =1; i <= n; i++)//记录频率
{
vts[i] += vis[i];
}
t++; //记录到达次数
return;
}
vis[x] = 1;
for (int i = 0; i < g[x].size(); i++)//访问邻接表
{
if (vis[g[x][i]] == 0) dfs(g[x][i]);
}
vis[x]=0;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> u >> v;
g[u].push_back(v);//无向图双向赋值
g[v].push_back(u);
}
cin >> u >> v;
dfs(u);
for (int i = 1; i <=n; i++)
{
if (vts[i] == t&&t!=0) k++;
}
cout << k;
}
用Python实现
cnt = 0
def dangerCoefficient(m,portal,cor,start,end):
if cor == m:
return cnt
a = portal[cor][0]
b = portal[cor][1]
if b == end:
cnt += 1
return cnt
if a == start:
cnt += 1
dangerCoefficient(m, portal, cor + 1, b, end)
n,m = map(int,input().split())
portal = []
gird = [[0 for _ in range(0,n+1)] for _ in range(0,n+1)]
visited = [0 for _ in range(0,n+1)]
path = [0 for _ in range(0,n+1)]
times = [0 for _ in range(0,n+1)]
for i in range(m):
portal.append(list(map(int,input().split())))
gird[portal[i][0]][portal[i][1]] = 1
gird[portal[i][1]][portal[i][0]] = 1 # 对称矩阵，无向的
def DFS(start,end,index):
if start == end:
global cnt
cnt += 1
for j in range(1,index):
times[path[j]] += 1 # 不能在这里return，因为通道的两个数是无序的
for i in range(1,n+1):
if gird[start][i] == 1 and visited[i] == 0:
path[index] = i
visited[start], visited[i] = 1,1
DFS(i,end,index+1)
visited[i] = 0
if __name__ == '__main__':
count = 0
start,end = map(int,input().split())
DFS(start,end,1)
for index,val in enumerate(times): # 注意enumerate最后返回的顺序是--（位置，值）！！！
if val == cnt and index != start and index != end: # 注意关键点不能为起点或者终点
count += 1
if cnt == 0: # 一条路径都找不出来
print("-1")
exit()
print(count)
# print(dangerCoefficient(m,portal,0,start,end))
上一篇： 深度优先遍历和广度优先遍历
下一篇： BFS（广度优先搜索）