Minimum Spanning Tree

Acyclic Graph

A cycle is a path that starts and ends at the same vertex and includes at least one edge. Also know as a "closed path." Having at least one edge means at least two vertices in the path: the start/end and one other.

A simple cycle is a cycle that includes vertices other than the start/end at most once.

A acyclic graph is a graph having no cycle.

Recall: a graph is connected if there is a path between every pair of vertices.

A connected acyclic graph is called a tree!

• a tree is assumed to be undirected because a "connected" graph is generally defined as an undirected graph.
• It's possible to define MST for directed graphs, still it is usually given other names like optimum branching, min-cost arborecence, etc.

Spanning Tree

A spanning tree of a connected undirected graph G is a subgraph of it that spans G.

A graph may have several spanning trees and can be built with a simple BFS or DFS of the graph.

Minimum Spanning Tree

A minimum spanning tree of a weighted graph G i a spanning tree of it with the minimum possible total edge weight.

• It is not unique and there could be many MSTs with the same total weight.

The MST Problem: Given a connected, undirected weighted graph G = (V, E, w), the minimum weight spanning tree problem requires finding a spanning tree of minimum weight, where the weight of a tree T is defined as the sum of the weight of all its edges: $w(T) = \Sigma w(e)$

Algorithms to Solve MST Problem

These two algorithms will produce the same MST if there is only one combination of the minimum.

Prim's Algoirthm

A greedy algoirthm that starts from a source vertex and spans the entire graph.

1. Start with a minimum spanning tree $T = \{\}$ (O(1))
2. Pick a vetex $v$ at random and add it to $T$. (O(1))
3. Choose a vertex $u$ not in $T$, such that the edge weight from a vertex in $T$ to $u$ is the least among all such edges. (O(M))
4. Add $u$ to $T$.
5. Repeat until ($N-1$) edges were added.

To implement, a priority queue is needed. And the most expensive part will be adding insertion/removal.

• You will be keeping all the edges that have one endpoint in $T$ in a min-heap and remove the best at each iteration.

The entire Prim's Algorithm will be M(log M).

Kruskal's Algoirhtm

A greedy algorithm that grows a forest of minimum spanning trees and combines them into one MST:

1. Sort all the edges in ascending order based on weight
2. Start with an empty minimum spanning tree $T = \{\}$
3. Pick the smallest edge and add to $T$
4. Add next smallest edge to $T$ unless it creates a cycle
5. Repeat the last step until ($N-1$) edges were added.

Building with sorted array of edges that has a pointer to the next position or keeping the edges in a (min-heap) priority queue ends up in the same space and time cost. Both sorting algorithms will be O(M lg M) runtime.

How do you check if the next min-weight edge $(v,w)$ is found?

• To check that it wont form a cyclic path, you must perform a BFS/DFS to check. These search algorithms are O(N+M).

Kruskal's algorithm is quadratic. However, we can improve the performance by using another data structure called union-find for efficiently checking/preventing cycles.