WikiGalaxy
Graph Prim's Algorithm
Introduction to Prim's Algorithm
Understanding Prim's Algorithm
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
Steps Involved
The algorithm operates by building the spanning tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
Example 1: Simple Graph
Graph Description
Consider a graph with vertices A, B, C, and D with the following edges and weights: AB=1, AC=3, AD=4, BC=2, BD=5, CD=6.
Applying Prim's Algorithm
Starting from vertex A, the algorithm will choose the edge AB (weight 1), then BC (weight 2), and finally CD (weight 6) to form the minimum spanning tree.
Graph:
A --1-- B
| \ |
3 4 2
| \ |
C --6-- D
Minimum Spanning Tree:
A --1-- B --2-- C
|
C --6-- D
Example 2: Complete Graph
Graph Description
Consider a complete graph with vertices P, Q, R, and S with edges PQ=2, PR=3, PS=4, QR=5, QS=6, RS=7.
Applying Prim's Algorithm
Starting from vertex P, the algorithm selects PQ (weight 2), QR (weight 5), and RS (weight 7) to form the minimum spanning tree.
Graph:
P --2-- Q
|\ /|
| 3\ /5 |
| X |
| / \ |
R --7-- S
Minimum Spanning Tree:
P --2-- Q --5-- R
|
R --7-- S
Example 3: Sparse Graph
Graph Description
Consider a sparse graph with vertices X, Y, Z, and W with edges XY=4, YZ=1, WX=3.
Applying Prim's Algorithm
Starting from vertex X, the algorithm selects XY (weight 4) and YZ (weight 1) to form the minimum spanning tree, leaving W disconnected due to lack of edges.
Graph:
X --4-- Y
| |
3 1
| |
W Z
Minimum Spanning Tree:
X --4-- Y --1-- Z
Example 4: Weighted Graph
Graph Description
Consider a weighted graph with vertices M, N, O, P, and Q with edges MN=2, MO=3, NP=4, OP=5, PQ=1.
Applying Prim's Algorithm
Starting from vertex M, the algorithm selects MN (weight 2), NP (weight 4), PQ (weight 1), and OP (weight 5) to form the minimum spanning tree.
Graph:
M --2-- N
| \ /|
3 4 1 |
| \/ |
O --5-- P --1-- Q
Minimum Spanning Tree:
M --2-- N --4-- P
| |
O --5-- P --1-- Q
Example 5: Disconnected Graph
Graph Description
Consider a disconnected graph with two components: A-B-C and D-E with edges AB=3, BC=2, DE=1.
Applying Prim's Algorithm
Prim's algorithm will only find the minimum spanning tree for the connected components separately, resulting in two separate trees.
Graph:
A --3-- B --2-- C
D --1-- E
Minimum Spanning Trees:
A --3-- B --2-- C
D --1-- E
