10. Minimum Spanning Tree using Prims Algorithm

In [2]:

from utils.graph import GraphAdjMatrix as Graph

from utils.graph import GraphAdjMatrix as Graph

In [3]:

num_vertices = 5

num_vertices = 5

In [4]:

g = Graph(num_vertices=num_vertices)

g = Graph(num_vertices=num_vertices)

In [5]:

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]:

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]:

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]:

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]:

prims_MST(g.graph, num_vertices)

prims_MST(g.graph, num_vertices)

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

In [ ]: