Rustでグラフ

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。10章のグラフと木。

（有向/無向）グラフと（有向）重み付きグラフを実装する。

use proconio::input;

type Graph = Vec<Vec<usize>>;

fn input_graph(use_default_values: bool) -> (usize, u64, Graph) {
    if use_default_values {
        // 頂点数と辺数
        let n = 8;
        let m = 12;

        // グラフ
        let g = vec![
            vec![5],
            vec![3, 6],
            vec![5, 7],
            vec![0, 7],
            vec![1, 2, 6],
            vec![],
            vec![7],
            vec![0],
        ];
        return (n, m, g);
    } else {
        println!("Input graph:");
        input! {
            // 頂点数と辺数
            n: usize,
            m: u64,
            // グラフ
            a_b_pairs: [(usize, usize); n],
        }
        let mut g = vec![vec![]; n];
        for ab in a_b_pairs {
            g[ab.0].push(ab.1);
            // 無向グラフの場合は以下を追加
            // g[ab.1].push(ab.0);
        }
        return (n, m, g);
    }
}

// ここでは重みを表す型を i64 型とする
#[derive(Clone)]
struct Edge {
    to: usize, // 隣接頂点番号
    w: i64,    // 重み
}

// 各頂点の隣接リストを，辺集合で表す
type WeightedGraph = Vec<Vec<Edge>>;

fn input_weighted_graph(use_default_values: bool) -> (usize, u64, WeightedGraph) {
    if use_default_values {
        // 頂点数と辺数
        let n = 8;
        let m = 12;

        // グラフ
        let g = vec![
            vec![Edge { to: 5, w: 1 }],
            vec![Edge { to: 3, w: 1 }, Edge { to: 6, w: 1 }],
            vec![Edge { to: 5, w: 1 }, Edge { to: 7, w: 1 }],
            vec![Edge { to: 0, w: 1 }, Edge { to: 7, w: 1 }],
            vec![
                Edge { to: 1, w: 1 },
                Edge { to: 2, w: 1 },
                Edge { to: 6, w: 1 },
            ],
            vec![],
            vec![Edge { to: 7, w: 1 }],
            vec![Edge { to: 0, w: 1 }],
        ];
        return (n, m, g);
    } else {
        println!("Input graph:");
        input! {
            n: usize,
            m: u64,
            a_b_w: [(usize, usize, i64); n],
        }
        let mut g = vec![vec![]; n];
        for abw in a_b_w {
            g[abw.0].push(Edge {
                to: abw.1,
                w: abw.2,
            });
        }
        return (n, m, g);
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust