图论篇--代码随想录算法训练营第五十天打卡| 深度优先搜索理论基础，98. 所有可达路径，广度优先搜索理论基础

本文主要是介绍图论篇--代码随想录算法训练营第五十天打卡| 深度优先搜索理论基础，98. 所有可达路径，广度优先搜索理论基础，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

深度优先搜索理论基础

DFS模板：

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

98. 所有可达路径

题目链接：98. 所有可达路径

题目描述：

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

解题思路：

该题目是深度优先搜索的一个简单应用。本题的关键是

1. 熟悉深搜模板
2. 存储方式--本题采用邻接表存储，如下图所示。

 

代码：

#include<iostream>
#include<vector>
#include<list>
using namespace std;vector<int> path;
vector<vector<int>> result;void dfs(vector<list<int>>& nodes, int start, int end)
{if(start == end) {result.push_back(path);return;}for(auto node : nodes[start]){path.push_back(node);dfs(nodes,node,end);path.pop_back();}}int main()
{int n, m;cin >> n >> m;vector<list<int>> nodes(n+1);for(int i = 0; i < m; i++){int s,t;cin >> s >> t;nodes[s].push_back(t);}path.push_back(1);dfs(nodes,1,n);if(result.empty()) cout << "-1" << endl;for(auto v: result){for(int i = 0; i < v.size()-1; i++)cout << v[i] << " ";cout << v[v.size()-1] << endl;}return 0;
}

广度优先搜索理论基础

原理讲解：

用一个方格地图，假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位

置，那么BFS就是从四个方向走出第一步。

代码实现中，只要能找到一个能保存我们要遍历过的元素的容器就可以。此处可以选择栈和队列。

由于广搜不考虑转圈搜索的顺序，因此当前栈和队列使用时没有区别。

BFS模板： 

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}}

这篇关于图论篇--代码随想录算法训练营第五十天打卡| 深度优先搜索理论基础，98. 所有可达路径，广度优先搜索理论基础的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---