Implementation (Part 2)

Lesson 6 of 9 in Coddy's Kruskal's Algorithm - Graph Algorithms course.

Now add the cheapest safe edge until the MST is complete.

Challenge

Medium

Now build the MST.

Write a function named kruskal that takes n and the flat edges array (triples, undirected) of a connected graph, and returns the total weight of its Minimum Spanning Tree.

Repeatedly take the cheapest unused edge; if its endpoints are in different sets, union them and add its weight; otherwise skip it.

Reuse the union-find idea from the previous lesson.

Try it yourself

#include <stdlib.h>

int kruskal(int n, int* edges, int edges_size) {
    // Write code here
    return 0;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Kruskal's Algorithm - Graph Algorithms

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Project lesson

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2