图论算法
是一类用来解决图论问题的算法。它们在计算机科学、运筹学、工程学等领域都有广泛应用。 图论算法是一类用来解决图论问题的算法。图论是离散数学的一个分支，研究图的学问。图是用来对对象之间的成对关系建模的数学结构，由“节点”或“顶点”以及连接这些顶点的“边”组成 图论算法在计算机科学、运筹学、工程学等领域都有广泛应用。例如，最短路径算法可以用来求解从一个顶点到另一个顶点的最短路径问题
图的基本概念：
图是一种由顶点和边组成的数据结构。根据边是否有方向，图可以分为有向图和无向图，无向图中的边没有方向，而有向图中的边有方向 ；
根据边是否有权值，图可以分为带权图和无权图，带权图是指图中的每条边都有一个数值或权值，用来表示长度、距离、时间或其他意义。每条边都带有权值的图称为带权图 。图可以用邻接矩阵或邻接表来表示。
图中的顶点可以有度数，表示与该顶点相连的边的数量。在有向图中，顶点还可以有入度和出度，分别表示指向该顶点和从该顶点指出的边的数量
路径是指从一个顶点到另一个顶点经过的一系列边。路径长度是指路径上边的数量。简单路径是指路径上顶点不重复出现的路径。回路是指起点和终点相同的路径，简单回路是指除起点和终点外，其余顶点不重复出现的回路
// 邻接矩阵表示无向图
let mut graph = vec![vec![0; 5]; 5];
graph[0][1] = 1;
graph[1][0] = 1;
graph[1][2] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[3][2] = 1;
graph[3][4] = 1;
graph[4][3] = 1;
// 邻接表表示无向图
let mut graph = vec![Vec::new(); 5];
graph[0].push(1);
graph[1].push(0);
graph[1].push(2);
graph[2].push(1);
graph[2].push(3);
graph[3].push(2);
graph[3].push(4);
graph[4].push(3);
图的遍历算法：
深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法。DFS 使用栈来实现，BFS 使用队列来实现。
深度优先搜索(DFS)
深度优先搜索（DFS）是一种沿着图的深度来遍历图的算法。
它从图的某个顶点开始，沿着当前顶点的边走到未访问过的顶点，然后继续从这个新顶点开始进行深度优先搜索，直到所有与当前顶点相连通的顶点都被访问过。然后回溯到上一个顶点，继续搜索下一个未访问过的顶点，直到所有顶点都被访问过。
下面是一个深度优先搜索的算法示例：
```
// 实现深度优先搜索算法
fn dfs(graph: &Vec<Vec<usize>>, v: usize, visited: &mut Vec<bool>) {
// 将起始节点标记为已访问
visited[v] = true;
// 输出起始节点的编号
println!("{}", v);
// 遍历与起始节点相邻的所有节点
for &w in &graph[v] {
// 如果 w 没有被访问过，那么就递归地对 w 进行深度优先搜索
if !visited[w] {
dfs(graph, w, visited);
}
}
这段代码是一个使用 Rust 语言实现的深度优先搜索（DFS）算法的例子。它接受三个参数：graph 是一个邻接表表示的图，v 是搜索的起始顶点，visited 是一个布尔类型的向量，用来记录每个顶点是否被访问过。
在函数体内，首先将 visited[v] 设为 true，表示顶点 v 已经被访问过。然后打印出顶点 v 的值。接下来，遍历顶点 v 的所有邻接顶点 w，如果 w 没有被访问过，则递归调用 dfs 函数，以顶点 w 为起始顶点继续进行深度优先搜索。
广度优先搜索（BFS）
广度优先搜索（BFS）是一种按照图的广度来遍历图的算法。它从图的某个顶点开始，首先访问这个顶点的所有未访问过的邻接顶点，然后再按照这些邻接顶点被访问的顺序依次访问它们的邻接顶点，直到所有与起始顶点相连通的顶点都被访问过。
下面是广度优先搜索的算法示例：
use std::collections::VecDeque;
// 实现广度优先搜索算法
fn bfs(graph: &Vec<Vec<usize>>, s: usize) {
// 创建一个布尔型向量来记录每个节点是否已经被访问过
let mut visited = vec![false; graph.len()];
// 创建一个双端队列来存储待访问的节点
let mut queue = VecDeque::new();
// 将起始节点标记为已访问，并将它加入队列中
visited[s] = true;
queue.push_back(s);
// 循环直到队列为空
while let Some(v) = queue.pop_front() {
// 输出当前节点的编号
println!("{}", v);
// 遍历与当前节点相邻的所有节点
for &w in &graph[v] {
// 如果 w 没有被访问过，那么就将它标记为已访问，并将它加入队列的后端
if !visited[w] {
visited[w] = true;
queue.push_back(w);
}
}
}
}
这段代码是一个使用 Rust 语言实现的广度优先搜索（BFS）算法的例子。它接受两个参数：graph 是一个邻接表表示的图，s 是搜索的起始顶点。
在函数体内，首先创建一个布尔类型的向量 visited，用来记录每个顶点是否被访问过。然后创建一个双端队列 queue，用来存储待访问的顶点。将起始顶点 s 标记为已访问，并将其加入队列。
接下来，进入一个循环，每次从队列的前端取出一个顶点 v，打印出它的值。然后遍历顶点 v 的所有邻接顶点 w，如果 w 没有被访问过，则将其标记为已访问，并将其加入队列。循环继续进行，直到队列为空。
最短路径算法：
Dijkstra 算法和 Floyd 算法是两种常用的最短路径算法。Dijkstra 算法适用于求单源最短路径，Floyd 算法适用于求所有点对之间的最短路径。
Dijkstra 算法
Dijkstra 算法是一种单源最短路径算法，它可以求出从图中某个顶点出发到其他所有顶点的最短路径。它的基本思想是：每次找到离起始顶点最近的一个顶点，然后更新这个顶点的所有邻接顶点的最短路径。这个过程不断重复，直到所有顶点的最短路径都被确定。
use std::cmp::Reverse;
use std::collections::BinaryHeap;
// 实现迪杰斯特拉算法
fn dijkstra(graph: &Vec<Vec<(usize, i32)>>, s: usize) -> Vec<i32> {
let n = graph.len();
// 创建一个整型向量来记录从起始节点到每个节点的最短距离
let mut dist = vec![i32::MAX; n];
// 创建一个二叉堆来存储待访问的节点
let mut heap = BinaryHeap::new();
// 将起始节点的最短距离初始化为 0，并将它加入堆中
dist[s] = 0;
heap.push(Reverse((0, s)));
// 循环直到堆为空
while let Some(Reverse((d, v))) = heap.pop() {
// 如果当前节点的最短距离已经被更新过，那么就跳过它
if d > dist[v] {
continue;
}
// 遍历与当前节点相邻的所有节点
for &(w, weight) in &graph[v] {
// 如果从 v 到 w 的路径比当前已知的从起始节点到 w 的最短路径更短，那么就更新 w 的最短距离，并将它加入堆中
if dist[v] + weight < dist[w] {
dist[w] = dist[v] + weight;
heap.push(Reverse((dist[w], w)));
}
}
}
// 返回从起始节点到所有节点的最短距离
dist
}
这段代码是一个使用 Rust 语言实现的 Dijkstra 算法的例子。它接受两个参数：graph 是一个邻接表表示的带权图，其中每条边都有一个权值，表示从一个顶点到另一个顶点的距离；s 是起始顶点。
在函数体内，首先获取图中顶点的数量 n，然后创建一个整数类型的向量 dist，用来存储从起始顶点到其他所有顶点的最短距离。初始时，将所有顶点的最短距离设为正无穷大。然后创建一个二叉堆 heap，用来存储待访问的顶点。将起始顶点的最短距离设为 0，并将其加入堆中。
接下来，进入一个循环，每次从堆中取出距离起始顶点最近的一个顶点 v。如果这个顶点的最短距离已经被更新过，则跳过这个顶点。否则，遍历顶点 v 的所有邻接顶点 w，如果从 v 到 w 的距离加上 v 的最短距离小于 w 的最短距离，则更新 w 的最短距离，并将其加入堆中。循环继续进行，直到堆为空。
Floyd 算法
Floyd 算法是一种多源最短路径算法，它可以求出图中所有顶点之间的最短路径。它的基本思想是：对于图中的每一对顶点，尝试通过其他所有顶点来更新它们之间的最短路径。这个过程不断重复，直到所有顶点之间的最短路径都被确定。
// 实现弗洛伊德算法
fn floyd(graph: &mut Vec<Vec<i32>>) {
let n = graph.len();
// 遍历所有节点作为中间节点
for k in 0..n {
// 遍历所有节点对 (i, j)
for i in 0..n {
for j in 0..n {
// 检查是否存在一条经过 k 的路径使得从 i 到 j 的距离更短
graph[i][j] = graph[i][j].min(graph[i][k] + graph[k][j]);
}
}
}
}
这段代码是用来实现弗洛伊德算法的。它接受一个邻接矩阵 graph 作为输入，其中 graph[i][j] 表示从节点 i 到节点 j 的边的权重。这个算法会计算出所有节点之间的最短路径，并将结果存储在输入的邻接矩阵中。
代码中使用了三重循环，第一层循环遍历所有节点作为中间节点 k，第二层和第三层循环分别遍历所有节点对 (i, j)。对于每一对节点 (i, j)，算法会检查是否存在一条经过中间节点 k 的路径，使得从 i 到 j 的距离变得更短。如果存在这样的路径，那么就更新邻接矩阵中 i 和 j 之间的距离。
最小生成树算法：
Kruskal 算法和 Prim 算法是两种常用的最小生成树算法。Kruskal 算法适用于稀疏图，Prim 算法适用于稠密图。
Kruskal 算法
Kruskal 算法则是基于边的操作，将边按照权重从小到大排列，每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中
下面是算法示例：
use std::cmp::Reverse;
fn kruskal(n: usize, edges: &Vec<(usize, usize, i32)>) -> i32 {
let mut uf = UnionFind::new(n); // 创建一个并查集
let mut edges = edges.clone(); // 复制边集
edges.sort_by_key(|&(_, _, weight)| weight); // 将边按照权重从小到大排序
let mut res = 0; // 初始化结果为 0
for &(u, v, weight) in edges { // 遍历所有边
if uf.union(u, v) { // 如果两个端点不在同一个连通分量中，则将其加入生成树并累加权重
res += weight;
}
}
res // 返回结果
}
struct UnionFind {
parent: Vec<usize>, // 存储每个节点的父节点
}
impl UnionFind {
fn new(n: usize) -> Self {
Self { parent: (0..n).collect() } // 初始化每个节点的父节点为自身
}
fn find(&mut self, x: usize) -> usize { // 查找 x 节点所在连通分量的根节点
if self.parent[x] != x { // 如果 x 节点的父节点不是自身，则递归查找其父节点的根节点并进行路径压缩
self.parent[x] = self.find(self.parent[x]);
}
self.parent[x] // 返回根节点
}
fn union(&mut self, x: usize, y: usize) -> bool { // 合并 x 和 y 节点所在的连通分量
let px = self.find(x); // 查找 x 节点所在连通分量的根节点
let py = self.find(y); // 查找 y 节点所在连通分量的根节点
if px == py { // 如果两个根节点相同，则说明 x 和 y 节点已经在同一个连通分量中，返回 false
false
} else { // 否则将 y 节点所在连通分量的根节点的父节点设为 x 节点所在连通分量的根节点，返回 true
self.parent[py] = px;
true
}
}
}
这段代码是使用 Kruskal 算法来计算最小生成树的权值和。它接受节点数量和一个边的列表作为输入，其中每个元素是一个元组，表示边的两个端点和边的权重。代码中使用了并查集来判断两个节点是否在同一个连通分量中，每次从边集中取出权重最小且两个端点不在同一个连通分量中的边加入生成树中。最后返回所有加入生成树的边的权重之和。
Prim 算法
Prim 算法是一种贪心算法，从一个起点开始，每次选择与当前生成树相邻的最小边，将其加入生成树中，直到生成树包含所有节点为止。
下面是算法示例：
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn prim(graph: &Vec<Vec<(usize, i32)>>) -> i32 {
let n = graph.len();
let mut dist = vec![i32::MAX; n]; // 初始化所有节点的最短距离为无穷大
let mut heap = BinaryHeap::new(); // 创建一个最小堆
dist[0] = 0; // 将起点的最短距离设为 0
heap.push(Reverse((0, 0))); // 将起点加入堆中
let mut res = 0; // 初始化结果为 0
while let Some(Reverse((d, v))) = heap.pop() { // 取出堆顶元素
if d > dist[v] { // 如果堆顶元素的距离大于当前节点的最短距离，则跳过
continue;
}
res += d; // 将堆顶元素的距离累加到结果中
for &(w, weight) in &graph[v] { // 遍历与当前节点相邻的节点
if weight < dist[w] { // 如果边的权重小于相邻节点的最短距离，则更新相邻节点的最短距离并将其加入堆中
dist[w] = weight;
heap.push(Reverse((dist[w], w)));
}
}
}
res // 返回结果
}
这段代码是使用 Prim 算法来计算最小生成树的权值和。它接受一个邻接表表示的图作为输入，其中每个元素是一个元组，表示相邻节点和边的权重。代码中使用了一个最小堆来存储节点的最短距离，每次从堆中取出距离最小的节点并更新与其相邻节点的距离。最后返回所有节点的最短距离之和。
网络流算法：
Ford-Fulkerson 算法是一种常用的网络流算法。它可以求解最大流问题，并且可以推导出最小割定理。
fn ford_fulkerson(graph: &mut Vec<Vec<i32>>, s: usize, t: usize) -> i32 {
let n = graph.len();
let mut flow = 0; // 初始化最大流为 0
loop {
let mut prev = vec![None; n]; // 初始化前驱节点数组
dfs(graph, s, t, i32::MAX, &mut prev); // 从源点开始进行深度优先搜索寻找增广路
if prev[t].is_none() { // 如果汇点的前驱节点为 None，则说明没有找到增广路，退出循环
break;
}
let mut f = i32::MAX; // 初始化增广路上的最小残余容量为无穷大
let mut v = t; // 从汇点开始回溯增广路
while v != s { // 回溯到源点
if let Some(u) = prev[v] { // 如果当前节点的前驱节点不为 None，则更新最小残余容量并继续回溯
f = f.min(graph[u][v]);
v = u;
}
}
flow += f; // 将增广路上的最小残余容量累加到最大流中
v = t; // 从汇点开始回溯增广路
while v != s { // 回溯到源点
if let Some(u) = prev[v] { // 如果当前节点的前驱节点不为 None，则更新残余网络并继续回溯
graph[u][v] -= f;
graph[v][u] += f;
v = u;
}
}
}
flow // 返回最大流
}
fn dfs(
graph: &[Vec<i32>],
u: usize,
t: usize,
f: i32,
prev: &mut Vec<Option<usize>>,
) -> i32 {
if u == t { // 如果当前节点是汇点，则返回 f
return f;
}
for (v, w) in graph[u].iter().enumerate() { // 遍历与当前节点相邻的节点
if *w > 0 && prev[v].is_none() { // 如果边的残余容量大于 0 且相邻节点的前驱节点为 None，则继续搜索
prev[v] = Some(u); // 更新相邻节点的前驱节点为当前节点
let d = dfs(graph, v, t, f.min(*w), prev); // 继续搜索
if d > 0 { // 如果找到了增广路，则返回 d
return d;
}
}
}
return 0; // 没有找到增广路，返回 0
}
这段代码是使用 Ford-Fulkerson 算法来计算最大流。它接受一个邻接矩阵表示的图、源点和汇点作为输入，其中每个元素表示边的容量。代码中使用了增广路算法来寻找增广路并更新残余网络，每次从源点开始进行深度优先搜索，找到一条从源点到汇点的增广路并更新残余网络。最后返回最大流。
图论算法在计算机科学中扮演着重要角色。随着科技的发展，我们期待着更多高效、实用的图论算法被发明出来。 from刘金，转载请注明原文链接。感谢！
