---
tags: Graph Theory
title: Minimum Spanning Tree (unfinished)
---

## Prim's Algorithm

### Sample Code

---

## Kruskal's Algorithm

$\text{Input: } G=(V,E)\text{ and a weight function }w:V\times V\rightarrow\mathbb{R}$
$\text{Output: } T=(V,F) \text{ where }F\subseteq E\text{ and }T\text{ is a spanning tree of }G.$
$1~~~~F\leftarrow\varnothing$
$2~~~~\textbf{for each }e=\{u,v\}\text{ in }E \text{ ordered by }w(u,v)\text{ do}$
$3~~~~~~~~\textbf{if }\text{there is no cycle in }H=(V,F\cup e)\text{ do}$
$4~~~~~~~~~~~~F\leftarrow F\cup e$
$5~~~~~~~~\text{end }\textbf{if}$
$6~~~~\text{end }\textbf{for}$

### Sample Code

- **[DisjointSets](https://hackmd.io/@programmingNotes/disjointsetsDS)**

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