Skip to main content

Minimum Spanning Tree (MST)

INCLUDE

Kruskal's Algorithm​

namespace Graph {
    Graph<WeightedEdge> kruskal(Graph<WeightedEdge>& g) {
        int32_t n = static_cast<int32_t>(g.adj.size());
        int32_t m = static_cast<int32_t>(g.ed.size());
        Graph<WeightedEdge> t(n);

        DSU::DSU dsu(n);
        vector<int32_t> ed_idx_w_order(m);
        std::iota(ed_idx_w_order.begin(), ed_idx_w_order.end(), 0);
        std::sort(ed_idx_w_order.begin(), ed_idx_w_order.end(),
            [&](const int32_t& x, const int32_t& y) { return g.ed[x].w < g.ed[y].w; });

        for (auto& ed_idx : ed_idx_w_order) {
            auto& ed = g.ed[ed_idx];
            if (dsu.join(ed.u, ed.v)) t.addEdge(ed);
        }

        return t;
    }
}

int main() {
    int n, m; cin >> n >> m;

    Graph::Graph<Graph::WeightedEdge> g(n + 1);
    for (auto _ [[maybe_unused]] : std::views::iota(0, m)) {
        int u, v, w; cin >> u >> v >> w;
        g.addEdge({u, v, w});
    }
    
    Graph::Graph<Graph::WeightedEdge> t = Graph::kruskal(g);

    for (auto edges : t.adj) {
        for (int edge_idx : edges) {
            auto ed = t.ed[edge_idx];
            cout << ed.u << ' ' << ed.v << ' ' << ed.w << endl;
        }
    }
}

Prim's Algorithm​