Rust：图论算法-六虎

图论算法

是一类用来处理图论问题的算法。它们在核算机科学、运筹学、工程学等范畴都有广泛应用。
图论算法是一类用来处理图论问题的算法。图论是离散数学的一个分支，研讨图的学识。图是用来对目标之间的成对关系建模的数学结构，由“节点”或“极点”以及衔接这些极点的“边”组成图论算法在核算机科学、运筹学、工程学等范畴都有广泛应用。例如，最短途径算法能够用来求解从一个极点到另一个极点的最短途径问题

图的基本概念：

图是一种由极点和边组成的数据结构。依据边是否有方向，图能够分为有向图和无向图，无向图中的边没有方向，而有向图中的边有方向；

依据边是否有权值，图能够分为带权图和无权图，带权图是指图中的每条边都有一个数值或权值，用来表明长度、间隔、时间或其他含义。每条边都带有权值的图称为带权图。图能够用邻接矩阵或邻接表来表明。

图中的极点能够有度数，表明与该极点相连的边的数量。在有向图中，极点还能够有入度和出度，分别表明指向该极点和从该极点指出的边的数量

途径是指从一个极点到另一个极点通过的一系列边。途径长度是指途径上边的数量。简略途径是指途径上极点不重复呈现的途径。回路是指起点和结尾相同的途径，简略回路是指除起点和结尾外，其余极点不重复呈现的回路

// 邻接矩阵表明无向图
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刘金，转载请注明原文链接。感谢！

Rust：图论算法

图论算法

图的基本概念：

图的遍历算法：

深度优先查找(DFS)

广度优先查找（BFS）

最短途径算法：

Dijkstra 算法

Floyd 算法

最小生成树算法：

Kruskal 算法

Prim 算法

网络流算法：

相关文章

k8s踩坑历险记

2022年终总结，展望规划2023

Kotlin的语法糖到底有多甜？

17｜数据结构：软件系统核心部件哈希表，内存如何布局？

作者信息