mst_example.C File Reference

Minimum Spanning Tree algorithms: Kruskal and Prim. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <tpl_graph.H>
#include <Kruskal.H>
#include <Prim.H>
#include <tclap/CmdLine.h>

Include dependency graph for mst_example.C:

Go to the source code of this file.

Classes
struct	CableLength

Typedefs
using	LocationNode = Graph_Node< string >
using	CableArc = Graph_Arc< double >
using	NetworkGraph = List_Graph< LocationNode, CableArc >

Functions
NetworkGraph	build_campus_network ()
	Build a sample network graph.
NetworkGraph	generate_random_graph (size_t num_nodes, size_t num_edges, unsigned seed)
	Generate a random graph for performance testing.
void	print_mst (NetworkGraph &tree, const string &algorithm)
	Print MST result.
double	run_kruskal (NetworkGraph &g, NetworkGraph &tree, bool verbose)
	Run Kruskal's algorithm.
double	run_prim (NetworkGraph &g, NetworkGraph &tree, bool verbose)
	Run Prim's algorithm.
double	mst_total_weight (NetworkGraph &tree)
	Calculate total MST weight.
int	main (int argc, char *argv[])

Detailed Description

Minimum Spanning Tree algorithms: Kruskal and Prim.

This example demonstrates two classic greedy algorithms for finding the Minimum Spanning Tree (MST) of a weighted undirected graph. Both algorithms are optimal and produce an MST with the same minimum total weight; when multiple optimal MSTs exist, the chosen edge set can differ. The algorithms differ in their approach and performance characteristics.

What is a Minimum Spanning Tree?

Given a connected, undirected graph with weighted edges, a spanning tree is:

• A subgraph that connects all vertices
• A tree (connected, acyclic)
• Has exactly V-1 edges

A minimum spanning tree is the spanning tree with minimum total edge weight.

Key properties:

• Uniqueness: MST is unique if all edge weights are distinct
• Optimality: Both algorithms produce optimal solution
• Greedy choice: Locally optimal choices lead to globally optimal solution

Algorithms Compared

Kruskal's Algorithm (1956)

Strategy: Greedily add edges in order of increasing weight

Algorithm:

1. Sort all edges by weight (ascending)
2. Initialize empty MST
3. For each edge (in sorted order):
   - If adding edge doesn't create cycle:
     - Add edge to MST
   - Use Union-Find to check cycles efficiently
4. Return MST

Key insight: Add smallest edge that doesn't create cycle

Data structures:

• Edge sorting: O(E log E) for sorting
• Union-Find: O(α(V)) per edge check (effectively O(1))

Time complexity: O(E log E) = O(E log V)

• Dominated by sorting step

Space complexity: O(V) for Union-Find

Best for: Sparse graphs (E ≈ V)

Prim's Algorithm (1957)

Strategy: Grow MST from a starting vertex, always adding minimum edge

Algorithm:

1. Start with arbitrary vertex in MST
2. While MST has < V-1 edges:
   - Find minimum-weight edge connecting MST to non-MST vertex
   - Add edge and vertex to MST
3. Return MST

Key insight: Always add cheapest edge connecting current MST to outside

Data structures:

• Priority queue: Store edges from MST to outside vertices
• Binary heap: O(log V) per operation
• Fibonacci heap: O(1) amortized decrease-key

Time complexity:

• O(E log V) with binary heap
• O(E + V log V) with Fibonacci heap

Space complexity: O(V) for priority queue

Best for: Dense graphs (E ≈ V²)

Complexity Comparison

Algorithm	Time (Binary Heap)	Time (Fibonacci Heap)	Best For
Kruskal	O(E log E)	O(E log E)	Sparse (E ≈ V)
Prim	O(E log V)	O(E + V log V)	Dense (E ≈ V²)

Note: For sparse graphs, Kruskal is often faster. For dense graphs, Prim with Fibonacci heap is better.

When to Use Which?

Use Kruskal When:

✅ Graph is sparse (few edges) ✅ Edges already sorted (or sorting is cheap) ✅ Simple implementation preferred ✅ Parallel processing needed (edges independent)

Use Prim When:

✅ Graph is dense (many edges) ✅ Have good priority queue implementation ✅ Need to start from specific vertex ✅ Graph represented as adjacency matrix

Applications

Network Design

• Telecommunications: Minimum cost to connect all cities
• Computer networks: Minimum cost network topology
• Power grids: Minimum cost electrical grid
• Transportation: Minimum cost road/rail network

Cluster Analysis

• Data mining: Group similar data points
• Image segmentation: Group similar pixels
• Social networks: Find communities

Approximation Algorithms

• TSP approximation: Christofides algorithm uses MST
• Steiner tree: MST provides approximation
• Facility location: Network design problems

Other Applications

• Image processing: Image segmentation
• Pattern recognition: Feature grouping
• Circuit design: Minimum wire routing

Example: Network Design

Problem: Connect 5 cities with minimum cost

Cities: A, B, C, D, E
Possible connections with costs:
  A-B: 10, A-C: 15, B-C: 8, B-D: 12,
  C-D: 6, C-E: 9, D-E: 7

MST solution: Connect with minimum total cost

• Result: A-B (10), B-C (8), C-D (6), D-E (7)
• Total cost: 31

Usage

# Run MST comparison demo
./mst_example
 
# Run performance benchmark on a random graph
./mst_example --benchmark --nodes 1000 --edges 5000
 
# Benchmark with custom seed and verbose output
./mst_example --benchmark --nodes 2000 --edges 8000 --seed 123 --verbose

See also

Kruskal.H Kruskal's algorithm implementation

Prim.H Prim's algorithm implementation

union_find_example.C Union-Find (used by Kruskal)

heap_example.C Priority queues (used by Prim)

Author

Leandro Rabindranath León

Definition in file mst_example.C.

Typedef Documentation

CableArc

using CableArc = Graph_Arc<double>

Definition at line 214 of file mst_example.C.

LocationNode

using LocationNode = Graph_Node<string>

Definition at line 211 of file mst_example.C.

NetworkGraph

using NetworkGraph = List_Graph<LocationNode, CableArc>

Definition at line 217 of file mst_example.C.

Function Documentation

build_campus_network()

NetworkGraph build_campus_network

(

)

Build a sample network graph.

Represents buildings that need to be connected with network cables. Edge weights represent cable lengths (cost).

Library ----15---- AdminBldg ----20---- Gym
   |                  |                  |
  12                  8                 25
   |                  |                  |
SciLab -----10----- MainHall ----18---- Dorm
   |                  |                  |
  22                 14                 16
   |                  |                  |
ArtStudio ---9---- Cafeteria ---11--- Theater

Definition at line 248 of file mst_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

Referenced by main().

generate_random_graph()

NetworkGraph generate_random_graph	(	size_t	num_nodes,
		size_t	num_edges,
		unsigned	seed
	)

Generate a random graph for performance testing.

Definition at line 288 of file mst_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, num_nodes, rng, and Aleph::to_string().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 406 of file mst_example.C.

References abs(), build_campus_network(), generate_random_graph(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), mst_total_weight(), num_nodes, run_kruskal(), run_prim(), and Aleph::verbose.

mst_total_weight()

double mst_total_weight

(

NetworkGraph &

tree

)

Calculate total MST weight.

Definition at line 398 of file mst_example.C.

References GraphCommon< GT, Node, Arc >::get_arc_it(), and Aleph::maps().

Referenced by main().

print_mst()

void print_mst	(	NetworkGraph &	tree,
		const string &	algorithm
	)

Print MST result.

Definition at line 335 of file mst_example.C.

References GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), and Aleph::maps().

Referenced by run_kruskal(), and run_prim().

run_kruskal()

double run_kruskal	(	NetworkGraph &	g,
		NetworkGraph &	tree,
		bool	verbose
	)

Run Kruskal's algorithm.

Definition at line 360 of file mst_example.C.

References Aleph::maps(), print_mst(), and Aleph::verbose.

Referenced by main().

run_prim()

double run_prim	(	NetworkGraph &	g,
		NetworkGraph &	tree,
		bool	verbose
	)

Run Prim's algorithm.

Definition at line 379 of file mst_example.C.

References Aleph::maps(), print_mst(), and Aleph::verbose.

Referenced by main().