Minimum Spanning Trees

Greedy Algorithms
- Make a series of choices
- Choose the next activity based on current selections, without backtracking
- Ensure that at every step, the choice made does not eliminate the possibility of finding a successful outcome
- At every step, it should be possible to find an optimal solution consistent with the selections made so far.
- This leads to only one viable solution being constructed, affirming that the solution must be correct.

Consider an undirected weighted graph.
Example graph vertices: B, C, D, A, H, G, F, I, E with weights:
- A-B: 7
- A-C: 9
- A-D: 10
- B-D: 14
- C-H: 4
- C-G: 2
- D-E: 2
- D-F: 1
- E-F: 7
- E-I: 6
- F-I: 8
- F-G: 11
- G-H: 8
- H-A: 4
A spanning tree connects all vertices in a tree structure (connected graph, no cycles).
The cost of a spanning tree is the sum of the weights on its edges, as seen:
- Cost example: 67
Minimum spanning tree is one where the cost is minimized.
- Example MST with a cost of 37.

Used for various applications such as:
- Network design (e.g., connecting cities with roads, electricity, telephone)
- Cluster analysis (e.g., genetic distance)
- Image processing (e.g., image segmentation)
- Fundamental primitive for other graph algorithms.

MSTs may be unique depending on edge weight uniqueness.
Lemma: Let 𝐺 be a connected, weighted, undirected graph with all edge weights distinct. Then 𝐺 has a unique MST.
Proof outlined in homework requirements.

Introduction to two greedy algorithms for finding MSTs.
- Inductive proof strategy is applicable: if choices so far are consistent with an MST, then the next greedy choice also remains consistent.
Other proofs approaches can be referenced in the "Algorithms Illuminated" reading.

A cut represents a partition of the graph’s vertices into two parts.
- Example of a cut: {A,B,D,E} and {C,I,H,G,F}.
- Cuts may have disconnected parts.
- Valid cuts must not connect vertices and respect the current edge set.
An edge crossing a cut is defined as light if it has the minimum weight among edges that cross the cut.

If a cut respects a set S of edges, then if MST contains S, and there exists a light edge crossing the cut {u,v}, it concludes there's an MST that includes S ∪ {{u,v}}.
- Adding light edges is always a safe choice.

Assume the existence of a cut that respects S.
Assume S is part of some MST T.
Let {u,v} be the light edge crossing the cut.
If {u,v} is in T, we are done since T remains an MST.
If {u,v} is not in T, the addition creates a cycle with at least one other edge in T crossing the cut.
Swapping {u,v} with any edge {x,y} in the cycle keeps the spanning nature intact and maintains cost because {u,v} was the lightest edge.
Thus, T’ is still an MST.

Starting point for greedy MST construction, denoted as slowPrim(G=(V,E), starting vertex s):.
Initialize a minimum spanning tree MST and a set of visited vertices.
Algorithmic steps include:
1. Identify the lightest edge from the starting vertex.
2. Add the edge to MST and accompany its vertex in the visited set.
3. Proceed with iterations until all vertices are visited, always selecting the lightest valid edge.
Naive runtime is O(nm), where:
- n is for iterations and m is the number of edges.

{k[v]} denotes vertex distance from the current spanning tree, improving efficiency through vertex activation and edge evaluation:
- Running time similar to Dijkstra’s algorithm, potentially O(mlog(n)) using efficient data structures.

Alternative greedy algorithm focusing on:
- Sort edges in non-decreasing weight order.
- Union-find data structure manages connected components, ensuring no cycles.
- Pseudo-code highlights sorting, and merging edges into the MST without forming cycles within disjoint sets.
- Complexity includes edge sorting, repeated find and union operations across potential edges, total runtime O(mlog(n)).

Prim's: Builds a single tree from a starting point, better suited for dense graphs.
Kruskal's: Constructs a forest, more effective for sparse graphs and achievable through radix sort for efficiency.

Optimized MST algorithms suggest randomized O(m) and other efficient techniques, prompting further research in cutting-edge implementations.
Key takeaways include the principles of greedy algorithms and their applications in both Prim’s and Kruskal’s methods for MST, emphasizing selection based on light edges that do not negate potential success.