图论底子与遍历算法

图的逻辑结构及实在现

图是由节点和边构成的，边分为有向边和无向边，对应有向图和无向图，逻辑结构如下：

根据这个逻辑结构，我们可以实现每个节点：

1.  //节点需要存储自身的值，也需要存储与其邻接的节点
2.  struct Vertex{
3.      int val; //自身值
4.      vector<Vertex*> neighbors; //用vector(动态容器)存储指向邻接节点的指针
5.  }

复制代码

你有没有发现，这和我们之前实现多叉树简直千篇一律：

1.  strcut Treenode{
2.      int val;
3.      vetcor<Vertex*> neighbors;
4.  }

复制代码

所以，图本质上是高级一点的多叉树而已，实用于树的DFS(深度优先搜刮)/BFS(广度优先搜刮)全部实用于图。
我们知道，多叉树的存储直接实用节点和指针举行存储就好了，遍历是从根节点开始遍历。那图怎么存呢？图是不存在根节点这个概念的。
毗邻表和毗邻矩阵

相当于每个节点都是根节点，我们用毗邻表和毗邻矩阵来实现图。
比如还得刚才那幅图：

用毗邻表和毗邻矩阵的存储方式如下：

毗邻表很直观，我们把节点x的所以邻人存到一个列表里，然后把x和这个列表关联起来（一般的x节点中建立一个指针，指向这个列表），如许就可以通过节点x找到它的所有毗邻节点。
毗邻矩阵是一个二维布尔数组，我们权且称为matrix，如果节点Vertex(i)与Vertex(j)有关联，那么就把matrix[j]设为True
(上图中绿色的格子代表有关联)，如果想知道节点Vertex(i)的所有毗邻节点，去扫一圈matrix[....]就行了。

1.  //邻接表
2.  vector<int> graph[]; //用数据类型为vector<int>的数组来存储邻接节点
3.  ​
4.  //邻接矩阵 matrix[x][y]记录是否有一条x指向y的边
5.  bool graph[][];

复制代码

那么，这两种存储图的方式各有什么优劣呢？
毗邻表的好处就是占用的空间少，我们看上面毗邻矩阵的图，有很多非绿色部分，这些部分都是没有被利用上的。反观毗邻表，开发出来的所有vector空间都被利用上了。弊端是毗邻表不能快速判断两个节点之间是否关联，同样，先看毗邻矩阵，如果我们要判断节点x与节点y是否有关联，只必要判断graph[x][y]是否为True就好了。而毗邻表想要判断x是否与y有关联，则必要遍历graph[x]查看是否有y存在，如果有，才能阐明x有一条指向y的边。
所以，使用哪一种方式实现图，要看具体情况。

在常规的算法题中，毗邻表的使用会更频繁一些，紧张是因为操作起来比较简单，空间利用度高。但是毗邻矩阵也不能忽视，碰到必要快速判断两个节点是否有关联的场景，使用毗邻矩阵会大幅降低时间复杂度，同时一些隐晦性子可以借助精妙的矩阵运算展现出来。
度

末了，我们再明确一下图特有的【度(degree)】的概念，在无向图中，【度】就是每个节点相连的边的条数。
由于有向图有方向，所以有向图的每个节点的【度】被细分为【入度】和【出度】。
在底子图的底子上继承扩展出【有向加权图】、【无向加权图】等复杂图

有向加权图怎么实现，很简单：
我们在存储节点时，不但存储当前节点的所有毗邻节点，还要存储这个节点到每个毗邻节点的权重即可。
如果是毗邻矩阵，那就把matrix[x][y]的值改为x指向y边的权重即可，0表现没有连接。
实现代码如下：

1.  //有向有权图的邻接表
2.  vector< pair<int,int> > graph[] // pair[0]代表邻接节点的下标值,pair[1]代表指向邻接节点的
3.      
4.  //有向有权图的邻接矩阵
5.  int graph[][];
6.  //如果不能提前知道图中节点的个数，就用动态vector
7.  vector<vector<int>> graph;

复制代码

图的遍历

之前在学习数据结构和算法的框架头脑中说过，各种数据结构被发明出来无非就是为了遍历和访问，【遍历】是所有数据结构的底子。
图的逻辑结构和多叉树比较类似，所以图的遍历我们参考多叉树的遍历，多叉树遍历框架如下：

1.  void traverse(TreeNode* root){
2.      if(root == nullptr) return;
3.      //前序位置
4.      for(TreeNode* child : root->children){
5.          traverse(child);
6.      }
7.      //后序位置
8.  }

复制代码

但是，图结构中可能有环存在，当图不是连通图时。这时图被分为好几个连通族。简单来说，你从图中的某一个节点开始遍历，有可能走了一圈又回到了这个节点【此时我们只在此中的一个连通族举行了遍历，其他连通族和第一个遍历地点节点的连通族无节点相连，我们遍历不外去】，而树不会如许，树从根节点开始遍历，末了一定会遍历到叶子节点，绝不可能回到它自身。
所以，如果图包罗环【即图不是连通图，存在好几个连通族】，我们就必要借助visited[](记录节点是否被遍历过)数组举行辅助：

1.  //记录被遍历过的节点
2.  vector<bool> visited;   //如果已知图中所有节点个数n，则直接声明 vector<bool> visited[n];
3.  //记录从起点到当前节点的路径
4.  vector<bool> onPath;    //路径上的节点改为true即可
5.  ​
6.  //图的遍历框架
7.  void traverse(Graph graph,int s){   //注意：遍历图的时候要注意图是怎么存储的？是用邻接表存的还是邻接矩阵存的
8.      //如果已经遍历过了，则跳过（不走回头路）
9.      if(visited[s]) return;
10.      //经过节点s，标记为已遍历
11.      visited[s] = true;
12.      //做选择：标记节点s在路径上
13.      onPath[s] = true;
14.      
15.      //BFS 深度遍历
16.      for(int neighbor:graph.neighbors(s)){
17.          traverse(graph,neighbor);
18.      }
19.      //撤销选择:节点s离开路径
20.      onPath[s] = false;
21.  }

复制代码

注意visited[]和onPath[]的区别，因为二叉树算是特殊的图【连通图】，所以用二叉树的遍历过程来理解这两个数组的区别：

上述gif描述了递归变量二叉树的过程，在visited中被标记为true的节点用灰色表现，在onPath中被标记为true的节点用绿色表现。类比贪吃蛇游戏，visited记录蛇走过的格子，onPath记录蛇身。在图的遍历过程中，onPath可以用来判断是否成环，类似与贪吃蛇是否自己咬到自己。这下你能清楚理解visited与onPath的区别了吧。

   成环检测
  onPath[]如何判断图中是否含有环呢？拿贪吃蛇游戏作为例子，图中有环就代表着贪吃蛇自己咬到自己了。也就是说遍历到某个节点时，其所有毗邻节点全在onPath[]中，这时间再往记录路径中加入节点，会出现一个被记录两次的节点，这个节点就是连成环的关键节点。
一般我们在处置惩罚路径相干的题目中，这个onPath[]是一定会被用到的，比如拓扑排序。
别的，我们注意到，onPath[]的两步操作【做选择，撤销选择】在之前的文章【回溯/BFS/动态规划 焦点框架】中提到过。onPath[]的两步操作是在遍历的for循环之外举行的。和BFS焦点框架千篇一律，也就是说，onPath[]只关注节点自己，并不关注节点之间的连接。

   回顾一下回溯/BFS/动态规划焦点框架
  回溯框架关注节点与节点之间的连接，也就是树枝

1. .....
2. //遍历下一层
3. for(Node child : root->children){
4.      //做选择
5.      ......
6.      traverse(child);
7.      //撤销选择
8.      ......
9. }
11. BFS关注节点本身，每次都需要进入节点
13. .....
14. //做选择
15. ......
16. //遍历下一层
17. for(Node child : root->children){
18.      traverse(child);
19. }
20. //撤销选择
21. ......

复制代码

动态规划框架就是关注整个子树，框架代码这里就不给出了。
所以对于图的遍历，我们常用的算法是DFS与BFS算法。
说了这么多onPath[],我们再讨论下visited[]，其目的很明显了，由于图可能含有环，visited就是防止递归重复遍历同一个节点从而进入死循环。
如果题目显然不含环，就没须要使用visited[]了。
题目实践

LeetCode 797 所有可能

---

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[j]存在一条有向边）。

示例 1：

1.  输入：graph = [[1,2],[3],[3],[]]
2.  输出：[[0,1,3],[0,2,3]]
3.  解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

复制代码

示例 2：

1.  输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
2.  输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

复制代码

提示：

• n == graph.length
  
• 2 <= n <= 15
  
• 0 <= graph[j] < n
  
• graph[j] != i（即不存在自环）
  
• graph 中的所有元素 互不相同
  
• 保证输入为 有向无环图（DAG）
  

---

解题思路：

这道题很简单嘛，我们直接利用DFS遍历这个图。以 0 为出发点遍历这个图，同时利用onPath[]记录走过的路径，遍历到终点时将路径加入到存储结果的result中即可。
解题代码：

1.  class Solution {
2.  public:
3.      vector <vector<int>> result; //存放结果
4.      vector<int> onPath; //记录当前路径  //在vector中查找的时间复杂度为o(n)
5.      vector <vector<int>> allPathsSourceTarget(vector <vector<int>> &graph) {
6.          dfs(graph, 0);
7.          return result;
8.      }
9.  ​
10.      void dfs(vector <vector<int>> &graph, int n) {
11.          //dfs终止条件
12.          if (n == graph.size() - 1) {
13.              onPath.push_back(n);
14.              result.push_back(onPath);
15.              onPath.pop_back();
16.              return;
17.          }
18.          //做出选择
19.          onPath.push_back(n);
20.          //进入下一层
21.          for (int i = 0; i < graph[n].size(); i++) {
22.              //遍历下一层
23.              dfs(graph, graph[n][i]);
24.          }
25.          //撤销选择
26.          onPath.pop_back();
27.      }
28.  };

复制代码

末了总结一下，图的存储方式紧张有毗邻表和毗邻矩阵两种，无论什么花里胡哨的图，都可以用这两种方式去存储。
与图相干尚有很多风趣的算法：

• 二分图判定
  
• 环检测与拓扑排序
  
• 最小天生树
  
• Dijkstra最短路径算法
  

我们再看几道题：
LeetCode 133克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包罗它的值 val（int） 和其邻人的列表（list[Node]）。

1.  class Node {
2.      public int val;
3.      public List neighbors;
4.  }

复制代码

测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用毗邻列表表现。
毗邻列表 是用于表现有限图的无序列表的集合。每个列表都描述了图中节点的邻人集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：

1.  输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
2.  输出：[[2,4],[1,3],[2,4],[1,3]]
3.  解释：
4.  图中有 4 个节点。
5.  节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
6.  节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
7.  节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
8.  节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

复制代码

示例 2：

1.  输入：adjList = [[]]
2.  输出：[[]]
3.  解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

复制代码

示例 3：

1.  输入：adjList = []
2.  输出：[]
3.  解释：这个图是空的，它不含任何节点。

复制代码

提示：

• 这张图中的节点数在 [0, 100] 之间。
  
• 1 <= Node.val <= 100
  
• 每个节点值 Node.val 都是唯一的，
  
• 图中没有重复的边，也没有自环。
  
• 图是连通图，你可以从给定节点访问到所有节点。
  

   Related Topics
  深度优先搜刮
广度优先搜刮
图
哈希表

---

解题思路：

克隆图本质上就是在遍历图的底子上对每个节点举行深拷贝而已，一个节点只能被深拷贝一次，但却可以被观察到多次。

我提到了一个新名词“观察到”，和访问、遍历、以及深拷贝差别，“观察到”只是在遍历图中看到了节点，而这三个操作是看到了节点而且碰了节点，实着实在地进入了节点里面。
举个例子，我在遍历一个连通图时，我先遍历节点B，然后在节点B的所有邻人节点中选择一个最合适的节点举行遍历，这时间节点B有邻人节点A与节点C，我发现C才是我想到的下一节点，所以我进入节点C，不进入节点A。
在上述过程中，节点A被观察到，而节点C被遍历（访问）。
有些节点被观察到就可以立即遍历，有些节点观察到却不能被遍历，这是为什么呢？
很显然，每个节点只能被遍历一次，所以从来没有被遍历过的节点天然是一被观察到就立即被遍历，而遍历过的节点被观察到就只能跳过遍历咯。所以在遍历图的过程中，我们必要一个备忘录来辅助遍历，一般我们是用数组来作为备忘录记录节点是否被遍历，碰到 遍历过程中还必要遍历过的节点的部分元素 的情况，一般要考虑使用哈希表来作为备忘录。
有了以上这些知识储备，现在我们回到本题。刚刚说到了克隆图的本质：在遍历图的底子上对每个节点举行深拷贝，也就是说，遍历每个节点时，还必要创建一个深拷贝节点，并存储指向这个深拷贝节点的指针。
我们进一步分析，这个深拷贝节点不但是拷贝了节点值，还要拷贝原来节点的所有毗邻节点。怎么拷贝呢？按照遍历图的流程去看，我们深拷贝了某个节点以及此节点存储的值后，可以去观察它的所有毗邻节点，如果毗邻节点被访问过，我们就把备忘录中此毗邻节点的拷贝节点的指针加入到此节点的毗邻列表中，如果毗邻节点没有被访问过，则直接递归到访问此毗邻节点，举行同样的拷贝操作。
解题代码：

1.  //辅助备忘录，记录被访问过的节点
2.  unordered_map<Node*, Node*> visited;
3.  ​
4.  //采用DFS遍历方法
5.  Node* cloneGraph(Node* node){
6.      //判空
7.      if(node == nullptr){
8.          return node;
9.      }
10.      
11.      //查看是否在备忘录中
12.      if(visited.find(node) != visited.end()){ //在备忘录中
13.          return visited[node];
14.      }
15.      
16.      //不在备忘录中
17.      //拷贝节点
18.      Node* copyNode = new Node(node->val);
19.      visited[node] = copyNode;
20.      //拷贝列表
21.      for(auto& neighbor: node->neighbors){
22.          copyNode->neighbors.emplace_back(cloneGraph(node));
23.      }
24.      
25.      return copyNode;
26.  }

复制代码

以上就是图遍历的简单应用了，很简单，多练几道题就能轻松掌握。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。