# 10. Minimum Spanning Tree using Prims Algorithm

In [2]:

Copied!

```
from utils.graph import GraphAdjMatrix as Graph
```

from utils.graph import GraphAdjMatrix as Graph

In [3]:

Copied!

```
num_vertices = 5
```

num_vertices = 5

In [4]:

Copied!

```
g = Graph(num_vertices=num_vertices)
```

g = Graph(num_vertices=num_vertices)

In [5]:

Copied!

```
g.graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0],
]
```

g.graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0],
]

In [6]:

Copied!

```
g.graph
```

g.graph

Out[6]:

[[0, 2, 0, 6, 0], [2, 0, 3, 8, 5], [0, 3, 0, 0, 7], [6, 8, 0, 0, 9], [0, 5, 7, 9, 0]]

In [7]:

Copied!

```
def find_min_wt_node(weights, visited):
min_wt = float("inf")
min_idx = -1
for idx, weight in enumerate(weights):
if min_wt > weight and not visited[idx]:
min_wt = weight
min_idx = idx
return min_idx
```

def find_min_wt_node(weights, visited):
min_wt = float("inf")
min_idx = -1
for idx, weight in enumerate(weights):
if min_wt > weight and not visited[idx]:
min_wt = weight
min_idx = idx
return min_idx

In [14]:

Copied!

```
def prims_MST(graph, num_vertices):
"""
we define 3 most important list data structures here: weights, visited, parent
weights: store minimum weights corresponding to the edges.
visited: boolean list which keeps a track of visited nodes
parent: values correspond to the parent of the node in graph.
* The indices of these list correspond to the nodes in the graph
Args:
graph (_type_): Adjacency Matrix graph
num_vertices (_type_): # vertices in graph
"""
weights = [float("inf")] * num_vertices
visited = [False] * num_vertices
parent = [-1] * num_vertices
# we can start with any node so we start with the 0th and assign it's weight to 0
weights[0] = 0
# since our MST has to have the same number of nodes as in original graph
# we loop through through # edges to build an MST
for _ in range(num_vertices):
# find the node with minimum weight
min_wt_node = find_min_wt_node(weights, visited)
visited[min_wt_node] = True
# go to all the adjacent nodes of this node
for adj_node in range(num_vertices):
# three things to check here:
# * check for a valid graph edge: graph[min_wt_node][adj_node] != 0
# * check if this node is not already visited: not visited[adj_node]
# * compare weight of this adj node in weight array with weight from the graph node we are visiting:
# weight[adj_node] & graph[min_wt_node][adj_node]
# * if weight in the weight array is more then replace it with the weight from the visiting graph node:
# weight[adj_node] = graph[min_wt_node][adj_node]
# since this is minimum and it came from the visiting graph node, record it's parent to be visiting graph node:
# parent[adj_node] = min_wt_node
if (
graph[min_wt_node][adj_node] > 0
and visited[adj_node] == False
and weights[adj_node] > graph[min_wt_node][adj_node]
):
weights[adj_node] = graph[min_wt_node][adj_node]
parent[adj_node] = min_wt_node
print(parent)
```

def prims_MST(graph, num_vertices):
"""
we define 3 most important list data structures here: weights, visited, parent
weights: store minimum weights corresponding to the edges.
visited: boolean list which keeps a track of visited nodes
parent: values correspond to the parent of the node in graph.
* The indices of these list correspond to the nodes in the graph
Args:
graph (_type_): Adjacency Matrix graph
num_vertices (_type_): # vertices in graph
"""
weights = [float("inf")] * num_vertices
visited = [False] * num_vertices
parent = [-1] * num_vertices
# we can start with any node so we start with the 0th and assign it's weight to 0
weights[0] = 0
# since our MST has to have the same number of nodes as in original graph
# we loop through through # edges to build an MST
for _ in range(num_vertices):
# find the node with minimum weight
min_wt_node = find_min_wt_node(weights, visited)
visited[min_wt_node] = True
# go to all the adjacent nodes of this node
for adj_node in range(num_vertices):
# three things to check here:
# * check for a valid graph edge: graph[min_wt_node][adj_node] != 0
# * check if this node is not already visited: not visited[adj_node]
# * compare weight of this adj node in weight array with weight from the graph node we are visiting:
# weight[adj_node] & graph[min_wt_node][adj_node]
# * if weight in the weight array is more then replace it with the weight from the visiting graph node:
# weight[adj_node] = graph[min_wt_node][adj_node]
# since this is minimum and it came from the visiting graph node, record it's parent to be visiting graph node:
# parent[adj_node] = min_wt_node
if (
graph[min_wt_node][adj_node] > 0
and visited[adj_node] == False
and weights[adj_node] > graph[min_wt_node][adj_node]
):
weights[adj_node] = graph[min_wt_node][adj_node]
parent[adj_node] = min_wt_node
print(parent)

In [15]:

Copied!

```
prims_MST(g.graph, num_vertices)
```

prims_MST(g.graph, num_vertices)

[-1, 0, 1, 0, 1]

In [ ]:

Copied!

```
```