Implementation (Part 2)

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

Now grow the tree, always adding the cheapest crossing edge.

Challenge

Medium

Now grow the whole tree.

Write a function named prim that takes n and the flat edges array (triples, undirected) of a connected graph, and returns the total weight of the Minimum Spanning Tree, starting the tree from vertex 0.

Keep an inTree flag per vertex. Each round, find the cheapest edge with exactly one endpoint in the tree, add its weight, and bring its outside endpoint into the tree.

Try it yourself

#include <stdlib.h>

int prim(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 Prim'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