Prim's Algorithm in Graph
Welcome to our beginner's guide to Prim's Algorithm in Graph Theory! Prim's Algorithm is a fundamental method used to find the minimum spanning tree (MST) of a connected, undirected graph. Let's explore this important algorithm together!
Understanding the Problem Statement
Before delving into Prim's Algorithm, let's understand the problem it addresses. In graph theory, a spanning tree of an undirected graph is a subgraph that is a tree and connects all the vertices together without creating cycles.
The minimum spanning tree (MST) of a graph is the spanning tree with the smallest possible sum of edge weights. The goal of Prim's Algorithm is to find this minimum spanning tree efficiently.
What is Prim's Algorithm?
Prim's Algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It starts with an arbitrary vertex and grows the spanning tree by adding the shortest edge that connects a vertex in the tree to a vertex outside the tree. The process continues until all vertices are included in the tree.
Prim's Algorithm is named after Czech mathematician Vojtěch Jarník and computer scientist Robert C. Prim, who independently discovered it in the 1950s.
How does Prim's Algorithm Work?
Prim's Algorithm operates as follows:
- Start with an arbitrary vertex as the initial vertex.
- Initialize a set to store the vertices included in the MST (initially empty).
- While there are vertices not yet included in the MST:
- Find the minimum-weight edge that connects a vertex in the MST to a vertex outside the MST.
- Add the newly discovered vertex and edge to the MST.
- Continue until all vertices are included in the MST.
Prim's Algorithm ensures that the growing MST remains connected at each step and stops when all vertices are included in the tree.
Prim's Algorithm for Minimum Spanning Tree (MST)
Let's explore Prim's Algorithm step by step to find the Minimum Spanning Tree (MST) of the following weighted graph:
A---2---B
/ \ |
1 3 4
/ \ |
C---5---D---E
Prim's Algorithm Steps:
- Start with an empty set to represent the MST. We'll begin with node A.
- Find the minimum-weight edge that connects a vertex in the MST to a vertex outside the MST. Add the vertex to the MST.
- Repeat step 2 until all vertices are included in the MST. Continue with vertex C:
- Find the minimum-weight edge connecting C to the MST (A).
- Continue with vertex B:
- Find the minimum-weight edge connecting B to the MST (A).
- Continue the process until all vertices are included:
- Connect D to the MST (A).
MST: {A}
MST: {A, C}
MST: {A, C, B}
MST: {A, C, B, D}
MST: {A, C, B, D, E}
The final Minimum Spanning Tree (MST) is represented by the set of edges:
A---2---B
\
1
\
C
\
5
\
D
\
4
\
E
Prim's Algorithm selects the minimum-weight edges to create the MST while ensuring that all vertices are included.
Example Application of Prim's Algorithm
Consider a scenario where you have a network of cities connected by roads, each road with a certain cost or distance. By applying Prim's Algorithm, you can determine the minimum cost to connect all cities with roads while ensuring that each city is reachable from any other city.
Implementing Prim's Algorithm in code
Now, let's take a look at how we can implement Prim's Algorithm in code. We'll provide examples in several programming languages to help you get started:
package codeKatha;
import java.util.*;
public class PrimMST {
public List<Edge> primMST(Graph graph) {
List<Edge> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
PriorityQueue<Edge> minHeap = new PriorityQueue<>((a, b) -> a.weight - b.weight);
// Start with an arbitrary vertex
int startVertex = 0;
visited.add(startVertex);
// Add all edges from the start vertex to the min heap
for (Edge edge : graph.getEdges(startVertex)) {
minHeap.add(edge);
}
while (!minHeap.isEmpty()) {
Edge edge = minHeap.poll();
int u = edge.source;
int v = edge.destination;
// If adding the edge forms a cycle, skip it
if (visited.contains(u) && visited.contains(v)) {
continue;
}
// Add the edge to the MST
result.add(edge);
visited.add(u);
// Add all edges from the newly added vertex to the min heap
for (Edge neighbor : graph.getEdges(v)) {
if (!visited.contains(neighbor.destination)) {
minHeap.add(neighbor);
}
}
}
return result;
}
}
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include "Graph.h"
class PrimMST {
public:
std::vector<Edge> primMST(Graph& graph) {
std::vector<Edge> result;
std::set<int> visited;
std::priority_queue<Edge, std::vector<Edge>, CompareEdge> minHeap;
// Start with an arbitrary vertex
int startVertex = 0;
visited.insert(startVertex);
// Add all edges from the start vertex to the min heap
for (Edge edge : graph.getEdges(startVertex)) {
minHeap.push(edge);
}
while (!minHeap.empty()) {
Edge edge = minHeap.top();
minHeap.pop();
int u = edge.source;
int v = edge.destination;
// If adding the edge forms a cycle, skip it
if (visited.count(u) && visited.count(v)) {
continue;
}
// Add the edge to the MST
result.push_back(edge);
visited.insert(v);
// Add all edges from the newly added vertex to the min heap
for (Edge neighbor : graph.getEdges(v)) {
if (!visited.count(neighbor.destination)) {
minHeap.push(neighbor);
}
}
}
return result;
}
};
class PrimMST:
def primMST(self, graph):
result = []
visited = set()
min_heap = []
# Start with an arbitrary vertex
start_vertex = 0
visited.add(start_vertex)
# Add all edges from the start vertex to the min heap
for edge in graph.get_edges(start_vertex):
heapq.heappush(min_heap, edge)
while min_heap:
edge = heapq.heappop(min_heap)
u, v, weight = edge.source, edge.destination, edge.weight
# If
adding the edge forms a cycle, skip it
if u in visited and v in visited:
continue
# Add the edge to the MST
result.append(edge)
visited.add(v)
# Add all edges from the newly added vertex to the min heap
for neighbor in graph.get_edges(v):
if neighbor.destination not in visited:
heapq.heappush(min_heap, neighbor)
return result
class PrimMST {
primMST(graph) {
const result = [];
const visited = new Set();
const minHeap = new PriorityQueue((a, b) => a.weight - b.weight);
// Start with an arbitrary vertex
const startVertex = 0;
visited.add(startVertex);
// Add all edges from the start vertex to the min heap
for (const edge of graph.getEdges(startVertex)) {
minHeap.add(edge);
}
while (!minHeap.isEmpty()) {
const edge = minHeap.poll();
const { source: u, destination: v } = edge;
// If adding the edge forms a cycle, skip it
if (visited.has(u) && visited.has(v)) {
continue;
}
// Add the edge to the MST
result.push(edge);
visited.add(v);
// Add all edges from the newly added vertex to the min heap
for (const neighbor of graph.getEdges(v)) {
if (!visited.has(neighbor.destination)) {
minHeap.add(neighbor);
}
}
}
return result;
}
}
Graph: Concept and Important Algorithms
1. Basics of Graph Data Structure2. Breadth-First Search (BFS) in Graph
3. Depth-First Search (DFS) in Graph
4. Topological Sort in Graph
5. Union-Find Algorithm in Graph
6. Prim's Algorithm in Graph
7. Dijkstra's Algorithm in Graph
8. Kruskal's Algorithm in Graph
Congratulations! You've now learned the basics of Prim's Algorithm in graph theory. Feel free to experiment with the provided code examples and explore further applications of Prim's Algorithm in your projects.
Comments
Post a Comment