Prim's algorithm is used to find the Minimum Spanning Tree (MST) of a weighted undirected graph. Here's the implementation of Prim's algorithm for an adjacency list representation:
import heapq
def prim_mst(graph):
num_vertices = len(graph)
visited = [False] * num_vertices
min_heap = []
mst_cost = 0
mst = []
# Start with the first vertex
heapq.heappush(min_heap, (0, 0)) # (weight, vertex)
while min_heap:
weight, current_vertex = heapq.heappop(min_heap)
# Skip if the vertex is already visited
if visited[current_vertex]:
continue
# Add current vertex to MST
mst.append(current_vertex)
mst_cost += weight
visited[current_vertex] = True
# Explore the neighboring vertices
for neighbor in graph[current_vertex]:
neighbor_vertex, neighbor_weight = neighbor
# Add unvisited neighbors to the heap
if not visited[neighbor_vertex]:
heapq.heappush(min_heap, (neighbor_weight, neighbor_vertex))
return mst, mst_cost
The graph parameter is an adjacency list representation of the graph, where each element of the list represents a vertex and its adjacent vertices along with the edge weights. Each adjacent vertex is represented as a tuple (vertex, weight).
Here's an example usage of the prim_mst function:
# Example graph represented as an adjacency list
graph = [
[(1, 5), (2, 1)],
[(0, 5), (2, 2), (3, 1)],
[(0, 1), (1, 2), (3, 4)],
[(1, 1), (2, 4)]
]
mst, mst_cost = prim_mst(graph)
print("Minimum Spanning Tree:", mst)
print("MST Cost:", mst_cost)
Minimum Spanning Tree: [0, 2, 1, 3] MST Cost: 6
The mst list represents the vertices in the minimum spanning tree, and mst_cost represents the total cost of the MST.
Certainly! Prim's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted undirected graph. The MST is a subgraph of the original graph that connects all vertices with the minimum total weight.
Here's a step-by-step explanation of how Prim's algorithm works -
Start with an empty MST and an empty set of visited vertices.
Choose an arbitrary vertex to start the algorithm. Add it to the MST and mark it as visited.
Consider all the edges connected to the current vertex. Add these edges to a priority queue (min heap) based on their weights.
Repeat the following steps until all vertices are visited or the priority queue is empty:
Extract the edge with the minimum weight from the priority queue.
If the extracted edge connects a visited vertex to an unvisited vertex:
Add the unvisited vertex to the MST.
Add the extracted edge to the MST.
Mark the unvisited vertex as visited.
Consider all the edges connected to the unvisited vertex and add them to the priority queue if the neighboring vertex is not visited.
The algorithm terminates when all vertices are visited or the priority queue becomes empty.
The MST obtained is the minimum spanning tree of the graph.
The key idea behind Prim's algorithm is to grow the MST by adding the edge with the minimum weight that connects a visited vertex to an unvisited vertex at each step. By iteratively adding such edges, the algorithm constructs the MST with the minimum total weight.
In the example code I provided earlier, the prim_mst function implements Prim's algorithm using an adjacency list representation of the graph. It maintains a minimum heap (min_heap) to efficiently extract the edge with the minimum weight at each step.
The algorithm continues until all vertices are visited or the priority queue is empty. The resulting MST is stored in the mst list, and the total cost of the MST is calculated and stored in the mst_cost variable.
I hope this provides a better understanding of Prim's algorithm for finding the MST using an adjacency list representation! Let me know if you have any more questions.