Kruskal's Algorithm

Kruskal's Algorithm - Course 3

F

F

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

int n; // number of vertices
vector<Edge> edges;

vector<Edge> kruskal() {
    vector<Edge> mst;
    sort(edges.begin(), edges.end());

    vector<int> tree_id(n);
    iota(tree_id.begin(), tree_id.end(), 0);

    for (Edge e : edges) {
        if (tree_id[e.u] != tree_id[e.v]) {
            mst.push_back(e);

            int old_id = tree_id[e.u];
            int new_id = tree_id[e.v];
            for (int i = 0; i < n; i++) {
                if (tree_id[i] == old_id) {
                    tree_id[i] = new_id;
                }
            }
        }
    }
    return mst;
}

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

int n; // number of vertices
vector<Edge> edges;

vector<Edge> kruskal() {
    vector<Edge> mst;
    sort(edges.begin(), edges.end());

    DSU dsu(n);
    for (int i = 0; i < n; i++) {
        dsu.make_set(i);
    }

    for (const Edge& e : edges) {
        if (dsu.find_set(e.u) != dsu.find_set(e.v)) {
            mst.push_back(e);
            dsu.union_sets(e.u, e.v);
        }
    }
    return mst;
}

Kruskal's Algorithm

Kruskal's Algorithm

Steps of the algorithm

Simple implementation

Faster implementation (Kruskal's algorithm)

Implementation