图理论基础

Algorithm

October 09, 2022

概念

假设图 G = {V, E}， V是顶点集，E是边集

边，无向边（edge）
有向边（arc） tail(起点) -> head（终点）
$\vert V\vert$: 点的个数，图的阶（order）
无根树，连通无向图
简单图 (simple graph)：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。因为最多n-1个不同的度，而有n个点，这叫做抽屉原理或者鸽巢原理。

反过来，如果一张图中有自环或重边，则称它为 多重图 (multigraph)。

参考这里

实现

本篇实现是诸多相关算法基础数据结构（邻接矩阵）：

额外依赖EasyColl gist

/// Adjacent link formed simple (directed) connected graph
#[derive(Default)]
pub struct Graph {
    pub e: MV<usize, usize>,
    pub w: M1<(usize, usize), isize>,
}


impl Graph {
    pub fn new() -> Self {
        Default::default()
    }

    /// The length of the shortest path between the most distanced nodes.
    pub fn diameter(&self) -> isize {
        diameter_dp(self)
    }

    /// O(|E|)
    pub fn vertexs(&self) -> impl Iterator<Item = usize> {
        let mut vertexs = HashSet::new();

        for (u, v, _w) in self.edges() {
            vertexs.insert(u);
            vertexs.insert(v);
        }

        vertexs.into_iter()
    }

    pub fn edges<'a>(
        &'a self,
    ) -> impl Iterator<Item = (usize, usize, isize)> + 'a {
        let mut edges = self.e.0.iter();
        let mut subedges = vec![];

        std::iter::from_fn(move || loop {
            if let Some((u, v)) = subedges.pop() {
                return Some((u, v, get!(self.w => (u, v))));
            } else {
                if let Some((from, tos)) = edges.next() {
                    subedges = tos
                        .into_iter()
                        .cloned()
                        .map(|v| (*from, v))
                        .rev()
                        .collect::<Vec<(usize, usize)>>();
                } else {
                    return None;
                }
            }
        })
    }
}