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).

- Kruskal's algorithm video explanation
- Another video explanation
- OO implementation of Kruskal's
- 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

## Discussion