Part of list:

Minimum Spanning Tree (Prim's algorithm and Kruskal's algorithm)

Minimum Spanning Tree (Prim's algorithm and Kruskal's algorithm)[ Edit ]

**Problem**: Given an *undirected weighted connected graph*, a minimum spanning tree (MST) is a subset of the edges of the graph which *forms a tree* and has the *minimum total edge weight*.

**Examples**:

**Prim's algorithm: **

Start with a arbitrary vertex as your tree. Grow your tree one vertex at a time by adding the minimum weight edge from a vertex in the current tree to a vertex not yet in the tree. If you so this using a min-heap, your algorithm run-time will be O(E log E). Since E <= V^2, this is also O(E log V).

**Kruskal's algorithm:**

Start with an empty tree. Iterate over the edges sorted by weight. If adding edge (u, v) to the current tree does not create a cycle, then add it, else discard it. If you use an adjacency list representation for the current tree, and a BFS / DFS to see if adding edge (u, v) forms a cycle, then your algorithm complexity is O(EV).

**Disjoint-set data-structure:**

However, checking if adding (u, v) forms a cycle can be done in O(log V) using a disjoint-set data structure giving a complexity of O(E log V). The Wikipedia article on Disjoint-set data structure is quite good (you only need the *Introduction* and *Disjoint-set forests *sections).

**Notes**: Although we covered the algorithms, we didn't prove of understand *why* they work. We'll explore separately in a follow-up discussion.

Read more…(237 words)

Mark as completed

Part of lists:

Previous

[CNTTREE] Trees Again

Next

Correctness of Prim's algorithm and Kruskal's algorithm

About the contributor:

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Loading…

Have a question? Ask here…

Post

Part of list:

Minimum Spanning Tree (Prim's algorithm and Kruskal's algorithm)

Contributor

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.