Try   HackMD

Prim's Algorithm

Sample Code


Kruskal's Algorithm

Input: G=(V,E) and a weight function w:V×VR
Output: T=(V,F) where FE and T is a spanning tree of G.

1    F

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

3        if there is no cycle in H=(V,Fe) do

4            FFe

5        end if

6    end for

Sample Code

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