【图论】（二）图论基础与路径问题

图的构造

这里仅对图论路径问题中图的构造做整理总结归纳，具体详细相关概念请参考代码随想录上的整理总结：

• 图论理论基础
• 深度优先搜索理论基础
• 所有可达路径-dfs实战
• 广度优先搜索理论基础

我们如何用代码来表示一个图呢？

一般使用邻接表、邻接矩阵或者用类来表示。

邻接矩阵

• 邻接矩阵使用二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
• 例如： grid[2][5] = 6，表示 节点 2 连接 节点5 为有向图，节点2 指向 节点5，边的权值为6。
• 如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6

• 在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间。

• 这种表达方式（邻接矩阵） 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。

• 而且在寻找节点连接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。

邻接矩阵的优点：

• 表达方式简单，易于理解
• 检查任意两个顶点间是否存在边的操作非常快
• 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

• 遇到稀疏图，会导致申请过大的二维数组造成空间浪费
• 遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费

邻接表

  邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

邻接表的构造如图：

 
这里表达的图是：

• 节点1 指向 节点3 和 节点5
• 节点2 指向 节点4、节点3、节点5
• 节点3 指向 节点4
• 节点4指向节点1

有多少边 邻接表才会申请多少个对应的链表节点。

从图中可以直观看出 使用 数组 + 链表 来表达 边的连接情况

邻接表的优点：

• 对于稀疏图的存储，只需要存储边，空间利用率高
• 遍历节点连接情况相对容易

缺点：

• 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
• 实现相对复杂，不易理解

所有可达路径

卡码网题目链接（ACM模式）

力扣题目链接 - 797. 所有可能的路径

题目描述：
  给定一个有 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  

提示信息：

 
写在前面：

• 在上述谈到图的两张存储方式中，这里通过两种方式逐一巩固。
• 此外，本题是目是深度优先搜索比较好的入门题，若对深搜不清楚的需先提前了解深度搜索理论与过程。

邻接矩阵存储

• 邻接矩阵 使用 二维数组来表示图结构， 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
• 本题有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请 n + 1 * n + 1 这么大的二维数组。

  vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
  

• 输入每行两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径，则表示 graph[s][t] = 1;，输入m条边程序则有：

  while (m--) {cin >> s >> t;// 使用邻接矩阵 ，1 表示 节点s 指向 节点tgraph[s][t] = 1;
  }
  

深搜三部曲：

1. 确认递归函数，参数

• 首先我们dfs函数一定要存一个图，用来遍历，需要存一个目前我们遍历的节点，定义为x
• 还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候 标明找到了终点
• 至于 单一路径 和 路径集合 可以放在全局变量，那么代码是这样的：

  vector<vector<int>> result; 	// 收集符合条件的路径
  vector<int> path; 				// 0节点到终点的路径
  // x：目前遍历的节点
  // graph：存当前的图
  // n：终点
  void dfs (const vector<vector<int>>& graph, int x, int n) {
  

2. 确认终止条件

当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。

// 当前遍历的节点x 到达节点n 
// 找到符合条件的一条路径
if (x == n) 
{ result.push_back(path);return;
}

3. 处理目前搜索节点出发的路径

接下来是走 当前遍历节点x的下一个节点。

首先是要找到 x节点指向了哪些节点呢？ 遍历方式是这样的：

for (int i = 1; i <= n; i++) 	// 遍历节点x链接的所有节点
{ if (graph[x][i] == 1) 		// 找到 x指向的节点，就是节点i{ 	}
}

接下来就是将 选中的x所指向的节点，加入到 单一路径来

path.push_back(i); // 遍历到的节点加入到路径中来

进入下一层递归

dfs(graph, i, n); // 进入下一层递归

最后就是回溯的过程，撤销本次添加节点的操作

path.pop_back(); // 回溯，撤销本节点

该过程整体代码：

for (int i = 1; i <= n; i++) 	// 遍历节点x链接的所有节点
{ if (graph[x][i] == 1)		// 找到 x链接的节点{path.push_back(i); 		// 遍历到的节点加入到路径中来dfs(graph, i, n); 		// 进入下一层递归path.pop_back(); 		// 回溯，撤销本节点}
}

程序实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>using namespace std;vector<vector<int>> result;		// 手机符合条件的路径
vector<int> path;				//0节点到终点的路径
// graph：存当前的图
// x：目前遍历的节点
// n：终点
void dfs(const vector<vector<int>> graph, int x, int n)
{// 当前遍历的节点x 到达节点n if(x == n){result.push_back(path);return;}// 遍历节点x链接的所有节点for(int i = 1; i <= n; i++){// 找到 x指向的节点，就是节点iif(graph[x][i] == 1){// 将选中的x所指向的节点，加入到 单一路径来。path.push_back(i);// 进入下一层递归dfs(graph,i,n);// 回溯的过程，撤销本次添加节点的操作path.pop_back();}}
}int main()
{// m条边 n个节点 // graph[s][t] = 1表示节点s可以指向tint m,n,s,t;cin >> n >> m;vector<vector<int>> graph(n+1, vector<int>(n+1,0));while(m--){cin >> s >> t;// 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的graph[s][t] = 1;}// 任何路径都是从节点1开始path.push_back(1);// 开始遍历dfs(graph,1,n);// 打印结果if(result.size() == 0)cout << -1 << endl;for(int i = 0; i < result.size(); i++){for(int j = 0; j < result[i].size() - 1; j++){cout << result[i][j] << " ";}cout << result[i][result[i].size() - 1] << endl;}return 0;
}

邻接表存储

  用邻接表存储和邻接矩阵存储的区别只需要修改图的定义存储、dfs函数内的参数以及对链表的遍历，核心框架、思路均不变。

程序实现：

//邻接表法
vector<vector<int>> result;		// 手机符合条件的路径
vector<int> path;				//0节点到终点的路径
// graph：存当前的图
// x：目前遍历的节点
// n：终点
void dfs(const vector<list<int>> graph, int x, int n)
{// 当前遍历的节点x 到达节点n if(x == n){result.push_back(path);return;}// 遍历节点x链接的所有节点for(int node: graph[x]){// 将选中的x所指向的节点，加入到 单一路径来。path.push_back(node);// 进入下一层递归dfs(graph,node,n);// 回溯的过程，撤销本次添加节点的操作path.pop_back();}
}int main()
{// m条边 n个节点 // graph[s][t] = 1表示节点s可以指向tint m,n,s,t;cin >> n >> m;vector<list<int>> graph(n+1);while(m--){cin >> s >> t;// 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的graph[s].push_back(t);}// 任何路径都是从节点1开始path.push_back(1);// 开始遍历dfs(graph,1,n);// 打印结果if(result.size() == 0)cout << -1 << endl;for(int i = 0; i < result.size();i++){for(int j = 0; j < result[i].size() - 1; j++){cout << result[i][j] << " ";}cout << result[i][result[i].size() - 1] << endl;}return 0;
}

字符串接龙

卡码网题目链接（ACM模式）

题目描述：

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：

• 序列中第一个字符串是 beginStr。
• 序列中最后一个字符串是 endStr。
• 每次转换只能改变一个字符。
• 转换过程中的中间字符串必须是字典 strList 中的字符串。

  给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。

输入描述：

  第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。

输出描述：

  输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。

输入示例：

6
abc def
efc
dbc
ebc
dec
dfc
yhn

输出示例：

4

提示信息： 从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4

 
本题只需要求出最短路径的长度就可以了，不用找出具体路径。

所以这道题要解决两个问题：

• 图中的线是如何连在一起的
• 起点和终点的最短路径长度

首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个。

所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。

然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。 因为广搜就是以起点中心向四周扩散的搜索。

本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。 而广搜只要达到终点，一定是最短路。

另外需要有一个注意点：

• 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
• 使用set来检查字符串是否出现在字符串集合里更快一些

程序实现：

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>using namespace std;int main()
{int n;string beginStr;string endStr;string str;unordered_set<string> strSet;	// 字典 存放每一个字符串cin >> n;cin >> beginStr >> endStr;for(int i = 0; i < n;i++){cin >> str;strSet.insert(str);}// 记录strSet里的字符串是否被访问过，同时记录路径长度unordered_map<string, int> visitMap; // <记录的字符串，路径长度>// 初始化队列queue<string> que;que.push(beginStr);// 加入队列即标记访问visitMap.insert(pair<string,int>(beginStr, 1));while(!que.empty()){// 获取队头字符串，拿出来string word = que.front();que.pop();// 这个字符串在路径中的长度为 visitMap[word]int path = visitMap[word];// 开始在这个str中，挨个字符去替换for(int i = 0; i < word.size(); i++){// 用一个新字符串替换str，因为每次要置换一个字符string newWord = word;// 遍历26的字母for(int j = 0; j < 26; j++){newWord[i] = j + 'a';// 发现替换字母后，字符串与终点字符串相同if(newWord == endStr){cout <<  path + 1 << endl; // 找到了路径 return 0;}// 字符串集合里出现了newWord，并且newWord没有被访问过if (strSet.find(newWord) != strSet.end() && visitMap.find(newWord) == visitMap.end()){// 添加访问信息，并将新字符串放到队列中visitMap.insert(pair<string, int>(newWord, path + 1));que.push(newWord);}}}}// 没找到输出0return 0;
}

有向图的完全可达性

卡码网题目链接（ACM模式）

题目描述：

  给定一个有向图，包含 N 个节点，节点编号分别为 1，2，…，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

输入描述：

  第一行包含两个正整数，表示节点数量 N 和边的数量 K。 后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。

输出描述： 如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

输入示例：

4 4
1 2
2 1
1 3
2 4

输出示例：

1

提示信息：

 
思路

本题给我们是一个有向图， 因此路径是存在方向的

递归三部曲：

1. 确认递归函数，参数

需要传入地图，当前的节点数（到当前节点是通路），同时还需要一个数组，用来记录我们都走过了哪些节点，这样好知道最后有没有把所有房间都遍历的。
所以 递归函数参数如下：

// key 当前的节点数（到当前节点是通路）
// visited 记录访问过的房间 
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {

2. 确认终止条件

遍历的时候，什么时候终止呢？这里有一个很重要的逻辑，就是在递归中，是处理当前访问的节点，还是处理下一个要访问的节点

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

代码就是这样的：

// 写法一：处理当前访问的节点
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {if (visited[key]) {return;}visited[key] = true;list<int> keys = graph[key];	// 获取当前节点连接的节点链表for (int key : keys) {// 深度优先搜索遍历dfs(graph, key, visited);}
}

如果我们是处理下一层访问的节点，而不是当前层。那么就要在 深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对 节点进行处理。

这样的话，就不需要终止条件，而是在 搜索下一个节点的时候，直接判断 下一个节点是否是我们要搜的节点。

代码就是这样的：

// 写法二：处理下一个要访问的节点
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {list<int> keys = graph[key];	// 获取当前节点连接的节点链表for (int key : keys){// 确认下一个是没访问过的节点if(visited[key] == false) {visited[key] = true;dfs(graph, key, visited);}}
}

可以看出，如何看待 我们要访问的节点，直接决定了两种不一样的写法

上述程序中，好像没有发现回溯的逻辑。本题是需要判断 1节点 是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？
当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”，

程序实现：

#include <iostream>
#include <vector>
#include <list>using namespace std;// key 当前得到的可以 
// visited 记录访问过的房间 
void dfs(vector<list<int>>& graph, int key, vector<bool>& visited)
{list<int> keys = graph[key];	// 获取当前节点下挂的节点链表for(int key: keys){if(visited[key] == false)	// 遍历每一个节点 并做dfs标记{visited[key] = true;dfs(graph,key,visited);}}
}int main()
{int n, m, s, t;cin >> n >> m;vector<list<int>> graph(n+1);while(m--){cin >> s >> t;graph[s].push_back(t);}vector<bool> visited(n + 1, false);visited[1] = true; 			// 节点1 预先处理dfs(graph, 1, visited);		// dfs计算能到达的最远节点，能到达并做标记for(int i = 1; i <= n; i++){if(visited[i] == false){cout << -1 << endl;	return 0;}}cout << 1 << endl;	return 0;
}