Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Minimum Spanning Tree

Explore how to find the minimum spanning tree (MST) of a connected, weighted, undirected graph using Prim's algorithm. Understand MST concepts, step through the algorithm to build the tree, and analyze the time and space complexity of the solution.

We'll cover the following...

Statement

Find the minimum spanning tree (MST)MST of a connected, undirected graph with weighted edges.

Example

Consider the following graph:

g a 1 b 2 a->b 1 c 3 a->c 1 b->c 2 d 4 b->d 3 e 5 c->e 3 d->e 2

The minimum spanning tree of the above graph is:

g a 1 b 2 a->b 1 c 3 a->c 1 b->c 2 d 4 b->d  3 e 5 c->e 3 d->e 2

Sample input

Input will be a graph of the form:

v = 5
e = [ [ 1, 2, 1 ],
      [ 1, 3, 1 ],
      [ 2, 3, 2 ],
      [ 2, 4, 3 ],
      [ 3, 5, 3 ],
      [ 4, 5, 2 ] ]

where vv is the number of edges, and ee is the set of weighted edges. Each edge is coded as follows: [source,destination,weight][source, destination, weight] ...