DFS/BFS专练-搞定图论基础！（从海岛问题过渡至图论基础应用C/C++)

:: 图论基础理论 :: 紧接着，图论基础理论中，咱们讲到，图论的遍历主要由（dfs与bfs决定）

那咱们本篇博客就来聊聊dfs与bfs。

dfs（深度优先搜索）、bfs（广度优先搜索）的区别：

• dfs（深度优先），就如名字一般，优先不断向下探索。不到黄河不回头，一直到达了绝境之后，才会回溯到原本的位置，然后换个方向，用同样的方式继续遍历。
• bfs（广度优先），优先遍历与本节点相连的所有节点。遍历完毕之后，到达下一个节点，继续用同样的方式遍历。

  为什么要讲两种遍历方式呢，因为在创建 邻接表 与 邻接矩阵 之后，想要运用，最基本的就是遍历。

  当然、想要掌握一个知识点，靠的从来不是纯概念。

  接下来，咱们用dfs遍历邻接表与邻接矩阵。用来练手。

  DFS（深度优先搜索）

  DFS（深度优先遍历）模版：

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

  那咱们根据例题，实战一下吧。

  98. 所有可达路径

  题目描述

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

  输入描述

  第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

  后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

  输出描述

  输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

  注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 `1 3 5`,而不是 `1 3 5 `， 5后面没有空格！

  输入示例

  5 5
  1 3
  3 5
  1 2
  2 4
  4 5

  输出示例

  1 3 5
  1 2 4 5
  

  提示信息

  

  用例解释：

  有五个节点，其中的从 1 到达 5 的路径有两个，分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

  因为拥有多条路径，所以输出结果为：

  1 3 5

  1 2 4 5

  或

  1 2 4 5

  1 3 5

  都算正确。

  数据范围：

  • 图中不存在自环
  • 图中不存在平行边
  • 1 > x >> y; // 在邻接矩阵中标记存在从节点 x 到节点 y 的有向边 arr[x][y] = 1; } // 首先将起始节点 1 存入当前路径 cur.emplace_back(1); // 从节点 1 开始进行深度优先搜索 dfs(1, n); // 如果没有找到从节点 1 到节点 n 的路径 if (res.size() == 0) { // 输出 -1 表示无解 cout >y; // 将终点 y 添加到起点 x 的邻接表中 graph[x].emplace_back(y); } // 将起点 1 添加到当前路径 cur 中 cur.emplace_back(1); // 从起点 1 开始进行深度优先搜索 dfs(1,n); // 如果结果集合 res 为空，说明没有找到从起点到终点的路径 if(res.size()==0) cout{0,1},{0,-1},{1,0},{-1,0}}; int result = 0; void bfs(const vector{0,1},{0,-1},{1,0},{-1,0}}; void dfs(const vector