loading...

Minimum Spanning Tree (Kruskal's Algorithm)

jjb profile image JB Updated on ・2 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources:

This post requires knowledge of graphs and union-find (covered in earlier posts).

  1. Kruskal's algorithm video explanation
  2. Another video explanation
  3. OO implementation of Kruskal's
  4. Wikipedia article on Minimum Spanning Tree

Takeaways:

  • A Minimum Spanning Tree (MST) is a subset of edges of an undirected, connected, weighted graph.
    • This means a MST connects all vertices together in a path that has the smallest total edge weight.
  • One algorithm for finding the MST of a graph is Kruskal's Algorithm.
  • Kruskal's algorithm is a greedy algorithm - this means it will make locally optimum choices, with an intent of finding the overall optimal solution.
  • Kruskal's algorithm relies on the union-find data structure.
    • First the algorithm sorts the graph's edges in ascending order (by weight).
    • Then for every edge, if it's vertices have different root vertices (determined by union-find's Find()), it will add the edge to a list & Union() it's vertices within the union-find data structure.
    • If roots are the same, it will skip the edge.
    • The final list represents the MST of the graph.
  • Another common algorithm for finding the MST of a graph is Prim's Algorithm. Commonly, Prim's uses a heap or priority queue in it's implementation.
  • Time complexity for Kruskal's algorithm is O(e log v) where e is the number of edges and v is the number of vertices in the graph. Space is O(e + v).

Below is my implementation of Kruskal's algorithm:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Apr 12 by:

Discussion

markdown guide