【杂乱笔记】图论

图论

图的存储与深度、广度遍历

基础定义

存储方式：

**邻接矩阵：**如果图有 N 个节点，那么矩阵的维度为 N×N，矩阵中的每个元素 A[i] [j] 表示节点 i 和节点 j 之间是否存在边。

[!NOTE]

邻接矩阵适用于稠密图

**邻接表：**在邻接表表示法中，每个节点都有一个列表，该列表存储与该节点直接相连的所有节点。

[!NOTE]

邻接表适用于稀疏图

遍历方式：

DFS（深度优先搜索）：从一个选定的节点开始，沿着每一条分支尽可能深入地探索，直到不能继续为止，然后回溯到上一个节点继续探索其他未访问的分支。

深搜三部曲：

1、确认递归函数，参数

2、确认终止条件（一般是判断是否visited）

[!NOTE]

在DFS中，栈在任何时刻都只包含从起始点的下一个点到当前探索点的路径,在岛屿问题中，如果岛屿退化成一条链，那么栈里就是岛屿上所有的土地-1。

BFS（广度优先搜索）：按层次逐层探索图，先访问当前深度层次的所有节点，然后再进入下一深度层次的节点。

[!NOTE]

在BFS中，队列在某些时刻可能会包含岛屿的所有或大部分土地节点，例如岛屿在某一"层"上的宽度或周长

• 如果岛屿是一条长链（1xN的形状），那么队列的最大大小将始终为1或2，因为在任何时候只有一个或两个节点正在被处理。
• 如果岛屿是一个正方形（NxN的形状），队列的最大大小可能接近岛屿的周长（4N-4）。

代码实现

DFS (邻接矩阵)

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<vector<int>>& graph, int x, int n) {// 当前遍历的节点x 到达节点n if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}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(); // 回溯，撤销本节点}}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));while (m--) {cin >> s >> t;// 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的graph[s][t] = 1;}path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}

DFS (邻接表)

#include<iostream>
#include<vector>
#include<list>
using namespace std;
vector<vector<int>> result;
vector<int>path;
void dfs(vector<list<int>>&graph,int x,int n){if(x==n){result.push_back(path);return;}for(int m:graph[x]){path.push_back(m);dfs(graph,m,n);path.pop_back();}
}int main(){int a,b;cin>>a>>b;vector<list<int>>graph(a+1);while(b--){int s,t;cin>>s>>t;graph[s].push_back(t);}path.push_back(1);dfs(graph,1,a);if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}

BFS (邻接矩阵)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;const int MAX_N = 1000;  // 最大顶点数
vector<vector<int>> graph(MAX_N, vector<int>(MAX_N, 0));
vector<bool> visited(MAX_N, false);
int n;  // 顶点数void bfs(int start) {queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int v = q.front();q.pop();cout << v << " ";for (int i = 0; i < n; i++) {if (graph[v][i] && !visited[i]) {q.push(i);visited[i] = true;}}}
}int main() {int m;  // 边数cin >> n >> m;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;graph[u][v] = graph[v][u] = 1;}bfs(0);  // 从顶点0开始BFSreturn 0;
}

BFS (邻接表)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;const int MAX_N = 1000;  // 最大顶点数
vector<vector<int>> graph(MAX_N);
vector<bool> visited(MAX_N, false);
int n;  // 顶点数void bfs(int start) {queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int v = q.front();q.pop();cout << v << " ";for (int u : graph[v]) {if (!visited[u]) {q.push(u);visited[u] = true;}}}
}int main() {int m;  // 边数cin >> n >> m;// 确保输入的顶点数不超过最大限制if (n > MAX_N) {cout << "顶点数超过最大限制" << endl;return 1;}// 读入边并构建图for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;// 确保顶点编号在有效范围内if (u >= 0 && u < n && v >= 0 && v < n) {graph[u].push_back(v);graph[v].push_back(u);} else {cout << "无效的顶点编号" << endl;return 1;}}bfs(0);  // 从顶点0开始BFSreturn 0;
}

其他补充

1、图的坐标轴与数学坐标轴不同，图以x轴垂直向下，y轴水平向右为正，对此dir数组的表示也不同。

上	下	左	右
{-1，0}	{1，0}	{0，-1}	{-1，0}

2、在二叉树中，深度优先遍历包括中序、前序、后序；广度优先遍历是层序遍历。

并查集

基础定义

并查集：是一种处理集合与集合关系的数据结构，主要包含查询两个元素是否属于同一集合和将两个不同的集合合成一个新的大集合。

• 查询（find）：是否同属于一个“父亲”
• 添加（join）：将两个集合添加进同一个“父亲”底下
• 路径压缩：为了使查找到效率达到O(1)，将同一棵树下的所有节点的父节点指向根节点。

代码实现

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}

按秩优化：

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;rank[i] = 1; // 也可以不写}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树else father[v] = u;if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}

最小生成树

基础定义

最小生成树（Minimum Spanning Tree, MST）是一个连通无向图的子图，它包含图中所有的顶点，并且边的权重之和最小。最小生成树具有以下特性：

1. 连通性：包含所有节点并保持连通。
2. 无环性：不包含环。
3. 最小权重：边的权重之和最小。

常用的算法有：

• Kruskal 算法：按权重升序对边排序，然后使用并查集逐步添加边，避免环的形成。
• Prim 算法：从任意节点开始，逐步扩展生成树，选择权重最小的边连接到未包含的节点。

代码实现

Kruskal算法

思路定义：

• 边的权值排序，因为要优先选最小的边加入到生成树里
• 遍历排序后的边
  • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
  • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

需求分析：

• 如何实现优先选择最小的边？（非for循环遍历）
  • 可以建立一个小顶堆，保证堆顶元素即为最小的边。
• 判断是否属于同一个集合？
  • 并查集。

具体代码：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// l,r为 边两边的节点，val为边的数值
struct Edge {int l, r, val;
};// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的，n要大一些// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}// 并查集的查找操作
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 并查集的加入集合
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}int main() {int v, e;int v1, v2, val;vector<Edge> edges;int result_val = 0;cin >> v >> e;while (e--) {cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}// 执行Kruskal算法// 按边的权值对边进行从小到大排序sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});// 并查集初始化init();// 从头开始遍历边for (Edge edge : edges) {// 并查集，搜出两个节点的祖先int x = find(edge.l);int y = find(edge.r);// 如果祖先不同，则不在同一个集合if (x != y) {result_val += edge.val; // 这条边可以作为生成树的边join(x, y); // 两个节点加入到同一个集合}}cout << result_val << endl;return 0;
}

时间复杂度：nlogn （快排） + logn （并查集） ，所以最后依然是 nlogn 。n为边的数量。

扩展

如果是要输出最小生成树都有哪些边

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Edge {int l, r, val;
};int n = 10001;vector<int> father(n, -1); void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); 
}void join(int u, int v) {u = find(u); v = find(v); if (u == v) return ; father[v] = u;
}int main() {int v, e;int v1, v2, val;vector<Edge> edges;int result_val = 0;cin >> v >> e;while (e--) {cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});vector<Edge> result; // 存储最小生成树的边init();for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result.push_back(edge); // 保存最小生成树的边result_val += edge.val; join(x, y);}}// 打印最小生成树的边for (Edge edge : result) {cout << edge.l << " - " << edge.r << " : " << edge.val << endl;}return 0;
}

prim算法

思路定义

1. 第一步，选距离生成树最近节点（val最小）
2. 第二步，最近节点加入生成树
3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

minDist数组 用来记录 每一个节点距离最小生成树的最近距离。

需求分析

需要个数组：

1、存图数组

2、最小生成树数组

3、minDist数组

4、是否已经在树中数组

代码实现：

#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;// 填一个默认最大值，题目描述val最大为10000vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;// 因为是双向图，所以两个方向都要填上grid[x][y] = k;grid[y][x] = k;}// 所有节点到最小生成树的最小距离vector<int> minDist(v + 1, 10001);// 这个节点是否在树里vector<bool> isInTree(v + 1, false);// 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起for (int i = 1; i < v; i++) {// 1、prim三部曲，第一步：选距离生成树最近节点int cur = -1; // 选中哪个节点 加入最小生成树int minVal = INT_MAX;for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始//  选取最小生成树节点的条件：//  （1）不在最小生成树里//  （2）距离最小生成树最近的节点if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 2、prim三部曲，第二步：最近节点（cur）加入生成树isInTree[cur] = true;// 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）// cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下// 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢for (int j = 1; j <= v; j++) {// 更新的条件：// （1）节点是 非生成树里的节点// （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小// 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 统计结果int result = 0;for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边result += minDist[i];}cout << result << endl;}

扩展

如果是把边记录下下来

#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;grid[x][y] = k;grid[y][x] = k;}vector<int> minDist(v + 1, 10001);vector<bool> isInTree(v + 1, false);//加上初始化vector<int> parent(v + 1, -1);for (int i = 1; i < v; i++) {int cur = -1;int minVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 记录边}}}// 输出 最小生成树边的链接情况for (int i = 1; i <= v; i++) {cout << i << "->" << parent[i] << endl;}
}

拓扑排序

基础定义

给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。

类似于大学排课，有一些课程需要其他课程学完了才能学，其他课程就称为该课程的依赖关系。

思路分析

1. 找到入度为0 的节点，加入结果集
2. 将该节点从图中移除

结果集的顺序，就是我们想要的拓扑排序顺序 （结果集里顺序可能不唯一）

这里可以采用广搜或者深搜。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap;// 记录文件依赖关系vector<int> result; // 记录结果while (m--) {// s->t，先有s才能有tcin >> s >> t;inDegree[t]++; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queue<int> que;for (int i = 0; i < n; i++) {// 入度为0的文件，可以作为开头，先加入队列if (inDegree[i] == 0) que.push(i);//cout << inDegree[i] << endl;}// int count = 0;while (que.size()) {int  cur = que.front(); // 当前选中的文件que.pop();//count++;result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]]--; // cur的指向的文件入度-1if(inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];} else cout << -1 << endl;}

最短路径

基础定义

在图中从一个起点到一个终点的路径，使得路径上边的权重之和最小。

1. Dijkstra算法：
   • 适用于非负权重图。
   • 使用优先队列逐步扩展最短路径。
2. Bellman-Ford算法：
   • 适用于有负权边的图。
   • 可以检测负权环。
3. Floyd-Warshall算法：
   • 适用于计算所有节点对之间的最短路径。
   • 使用动态规划解决。

代码实现

Dijkstra算法

通过贪心算法

1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

minDist数组 用来记录 每一个节点距离源点的最小距离。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;}int start = 1;int end = n;// 存储从源点到每个节点的最短距离vector<int> minDist(n + 1, INT_MAX);// 记录顶点是否被访问过vector<bool> visited(n + 1, false);minDist[start] = 0;  // 起始点到自身的距离为0for (int i = 1; i <= n; i++) { // 遍历所有节点int minVal = INT_MAX;int cur = 1;// 1、选距离源点最近且未访问过的节点for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}visited[cur] = true;  // 2、标记该节点已被访问// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径}

对于此也有优化版

代码随想录

Bellman-Ford算法

1. 初始化：
   • 将源点的距离初始化为 0，其他所有节点的距离初始化为正无穷大。
2. 松弛操作：
   • 对所有边进行 V−1 次迭代（V 是节点数）。
   • 对于每条边 (u,v)，如果 distance[u]+weight(u,v)<distance[v]，则更新 distance[v]。
3. 检测负权环：
   • 在第 V 次迭代中，再次尝试松弛所有边。
   • 如果还能更新任意节点的距离，则图中存在负权环。

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;// 将所有边保存起来for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;// p1 指向 p2，权值为 valgrid.push_back({p1, p2, val});}int start = 1;  // 起点int end = n;    // 终点vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛int from = side[0]; // 边的出发点int to = side[1]; // 边的到达点int price = side[2]; // 边的权值// 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price;  }}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径}

Floyd算法

Floyd-Warshall算法用于计算所有节点对之间的最短路径。它适用于带权有向图，可以处理负权边，但不能处理负权环。

1. 初始化：
   • 创建一个距离矩阵 dist，将每个节点对的距离初始化为边权重，对于没有直接边的节点对，初始化为正无穷大。
   • 对角线元素（自身到自身的距离）初始化为 0。
2. 动态规划：
   • 逐步引入每个节点作为中间节点，更新距离矩阵。
   • 对于每对节点 (i,j)，检查是否通过中间节点 kk 可以缩短路径： dist[i] [j]=min⁡(dist[i] [j],dist[i] [k]+dist[k] [j])
3. 检测负权环：
   • 如果在最终的距离矩阵中，任何 dist[i][i]dist[i][i] 变为负数，则存在负权环。

**dp数组的定义如下：**grid[i] [j] [k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。

#include <iostream>
#include <vector>
#include <list>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;// 创建一个三维向量 grid，用于存储节点之间的最短路径距离// 初始化为 10005，表示初始时节点之间不可达（假设边的最大权重为 10000）vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // 读取图的边信息for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;  // 设置 p1 到 p2 的初始距离grid[p2][p1][0] = val;  // 因为是无向图，所以还要设置 p2 到 p1 的距离}// 开始 Floyd-Warshall 算法for (int k = 1; k <= n; k++) {  // k 表示中间节点for (int i = 1; i <= n; i++) {  // i 表示起始节点for (int j = 1; j <= n; j++) {  // j 表示终止节点// 更新 i 到 j 的最短路径，考虑通过 k 的路径grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);}}}// 处理查询int z, start, end;cin >> z;while (z--) {cin >> start >> end;// 输出从 start 到 end 的最短路径// 如果距离仍为初始值 10005，表示不可达，输出 -1if (grid[start][end][n] == 10005) cout << -1 << endl;else cout << grid[start][end][n] << endl;}
}