Lib.rs

图库

快速入门

简单图遍历

use luka::Graph;
use luka::algorithms;
use luka::utils;

fn main() {
    let mut graph = Graph::new(100);

    graph.add_edge(1, 2, 0).unwrap();
    graph.add_edge(1, 3, 0).unwrap();
    graph.add_edge(2, 4, 0).unwrap();
    graph.add_edge(3, 4, 0).unwrap();
    graph.add_edge(4, 5, 0).unwrap();

    let start = graph.get_vertex(1).unwrap();
    let target = graph.get_vertex(5).unwrap();
    let parents = algorithms::bfs(&graph, &start).unwrap();
    match utils::find_path(&graph, &target, &parents).unwrap() {
        Some(path) => {
            assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 5]);
        }
        None => {
            println!("Path not found !!!")
        }
    }
}

使用访问者

use luka::Graph;
use luka::algorithms;
use luka::utils;

fn main() {
    struct CustomVisitor {
        visiting_order: Vec<usize>
    }

    impl <T> VisitorBFS<T> for CustomVisitor {
        fn queue_extract_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorBFSAction, GraphError> {
            self.visiting_order.push(vertex.id());
            Ok(VisitorBFSAction::Nothing)
        }
    }

    let mut graph = Graph::new(100);
    graph.add_edge(1, 2, 0.0).unwrap();
    graph.add_edge(2, 3, 0.0).unwrap();
    graph.add_edge(2, 4, 0.0).unwrap();
    graph.add_edge(2, 5, 0.0).unwrap();
    graph.add_edge(4, 8, 0.0).unwrap();
    graph.add_edge(8, 17, 0.0).unwrap();

    let mut visitor = CustomVisitor{ visiting_order: vec![] };
    let start = graph.get_vertex(1).unwrap();
    bfs_with_visitor(&graph, &start, &mut visitor).unwrap();

    assert_eq!(vec![1, 2, 3, 4, 5, 8, 17], visitor.visiting_order);
}

列表算法

• BFS

Breadth-first search (BFS) 是最简单的图遍历算法之一，是许多重要图算法的基础。算法复杂度 - O(|V| + |E|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• DFS

Depth-first search (DFS) - 图遍历的一种方法。算法复杂度 - O(|V| + |E|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• 查找连通分量

搜索连通分量。该算法与无向图一起工作。算法将图中的顶点分为几个组，使得在一个组内，可以从一个顶点到达任何其他顶点，但不同组之间没有路径。算法复杂度 - O(|V| + |E|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• 查找强连通分量

强连通分量是顶点的一个子集（最大包含），其中该子集中的任何两个顶点都是相互可达的。图是有向的。算法复杂度 - O(|V| + |E|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• 迪杰斯特拉算法

迪杰斯特拉算法是图上的一个算法。它从图的一个顶点找到到所有其他顶点的最短路径。该算法仅适用于没有负权边的图。算法复杂度 - O(|E| log |V|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• 拓扑排序

图的拓扑排序问题如下：指定其顶点上的这样一个线性顺序，使得任何边都从编号较小的顶点指向编号较大的顶点。显然，如果图有环，则不存在这样的顺序。算法复杂度 - O(|V| + |E|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• 在图（有向和无向图）中查找循环

算法复杂度 - O(|V| + |E|)，其中 |V| 是图中顶点的数量，|E| 是图中边的数量。

• 查找子树大小

该算法找到每个子树的大小。图必须是树，即连通无环图。算法复杂度 - O(|E|)，其中 |E| 是图中边的数量。

• 查找顶点深度

该算法找到每个顶点的深度。图必须是树，即连通无环图。算法复杂度 - O(|E|)，其中 |E| 是图中边的数量。

• 生成树（克鲁斯卡尔算法）

克鲁斯卡尔算法是一种高效的算法，用于构建加权无向连通图的最低生成树。算法复杂度 - O(|E| * log(|E|))，其中 |E| 是图中边的数量。

• 弗洛伊德算法

此算法用于在具有正或负边权重的加权图中寻找最短路径（但无负环）。算法复杂度 - O(|V|^3)，其中 |V| 是图中顶点的数量。

• 贝尔曼-福特算法

贝尔曼-福特算法是一种寻找加权图中最短路径的算法。与迪杰斯特拉算法不同，贝尔曼-福特算法允许边具有负权，但负权环仍然是不允许的。算法复杂度 - O(|E| * |V|)，其中 |E| 是图中边的数量，|V| 是图中顶点的数量。

• 最近公共祖先（LCA）

构建的算法复杂度 - O(n)。查询响应的算法复杂度 - O(log n)，其中 n 是树中的节点数。

• 寻找桥

在无向图中寻找桥。算法复杂度 - O(|E| + |V|)，其中 |E| 是图中边的数量，|V| 是图中顶点的数量。