Prim's Algorithm

Sample Code

---

Kruskal's Algorithm

$\text{Input: }G=(V,E)\text{ and a weight function }w:V\times V\to \mathbb{R}$

$\text{Output: }T=(V,F)\text{ where }F\subseteq E\text{ and }T\text{ is a spanning tree of }G.$

$1F\leftarrow \varnothing$

$2\mathbf{\text{for each }}e=\{u,v\}\text{ in }E\text{ ordered by }w(u,v)\text{ do}$

$3\mathbf{\text{if }}\text{there is no cycle in }H=(V,F\cup e)\text{ do}$

$4F\leftarrow F\cup e$

$5\text{end }\mathbf{\text{if}}$

$6\text{end }\mathbf{\text{for}}$

Sample Code

• DisjointSets

struct Edge {
    int u;
    int v;
    int w;

    bool operator<(const Edge& rhs) const { return w < rhs.w; }
};

vector<Edge> edges(m);
sort(edges.begin(), edges.end());

DisjointSets djs(n);
vector<vector<pii>> adj(n);
vector<bool> used(m, false);
ll res = 0;

for (int i = 0, j = 0; i < n - 1 && j < m; ++j) {
    auto [u, v, w] = edges[j];
    if (djs.find(u) == djs.find(v)) continue;
    djs.unite(u, v);
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
    used[j] = true;
    res += w;
    ++i;
}

Second Minimum Spanning Tree