Minimum Spanning Tree

Briefly discuss how calculating for an MST could be useful.

Calculating for a minimum spanning tree (MST) is useful when we want to minimize cost / weight of nodes that are connected multiple points of each other. One application of this is when we want to construct roads that have multiple points, we want to be as efficient as possible. I think MST is more of the algorithm that we use when we want to layout areas and different connections with the different areas. And for us to have efficiency in those connections, we would want to get the minimum cost of building and creating those connections.

Talk about how similar Prim’s algorithm is to Dijkstra’s.

Dijkstra’s algorithm is a rediscovery of Prim’s algorithm. They are similar such that they find the the least amount something. For Prim’s, it finds the least amount of weight that connects from the starting vertex, and then creates a tree – a minimum spanning tree. For Dijkstra’s, it finds the shortest path from the starting point to the end. Algorithm-wise, from the starting vertex, both algorithms find first the neighboring vertices that have the least amount of cost / weight. From there, they find the next vertices that also have the least amount of cost / weight. They are similar such that they are both greedy algorithms. At times, they can be inefficient because both would have to search for every possible neighboring vertices that have the least amount cost / weight.

Code Used:

from collections import defaultdict
import heapq # this module implements the Min-Heap

# adj_list = {
#     'A':{'Y':5, 'B':1},
#     'Y':{'A':5, 'X':5},
#     'X':{'Y':5, 'Z':5},
#     'Z':{'X':5, 'C':1, 'D':1},
#     'B':{'A':1, 'C':1, 'D':1},
#     'C':{'B':1, 'Z':1},
#     'D':{'B':1, 'Z':1}
# }


class Graph:
    def __init__(self):
        self.adj_list = {}

    def addEdge(self, i, j, w):
        if i in self.adj_list:
            self.adj_list[i].update({j:w})
        else:
            self.adj_list[i] = {j:w}
        
        if j in self.adj_list:
            self.adj_list[j].update({i:w})
        else:
            self.adj_list[j] = {i:w}


    def prims_algorithm(self, starting_vertex):
        total_weight = 0 # counter for the total weight
        
        mstSet = defaultdict(set) # creates a set that keeps track of vertices included in the MST
        visited_nodes = set([starting_vertex]) # creates a set the keeps track of visited nodes 

        edges = [
        (weight, starting_vertex, target)
        for target, weight in self.adj_list[starting_vertex].items()
        ] # creates a list of edges that consists of the weight, the source and the targe

        heapq.heapify(edges) # we use a heap to form our "tree". this arranges our starting edges to be used in adding more

        while edges: # while there are still edges in the list of edges for "traversal"
            weight, source, target = heapq.heappop(edges) # gets the each value of the edge from the list of edge and removes/pops it off the list of edges
            if target not in visited_nodes: # if the target node is not in the set of visited nodes
                visited_nodes.add(target) # add the target in the set of visited nodes; 
                mstSet[source].add(target) # add the target in the set for the vertices in the MST
                for next_target, weight in self.adj_list[target].items(): # looks into the graph (adjacency list) for the next_target and its weight from the target
                    if next_target not in visited_nodes: # if the next_target is not in the set of visited nodes,
                        heapq.heappush(edges, (weight, target, next_target)) # add/pushes this "edge" which consists of the target, the next_target and its weight in to the list of edges

        # print(self.adj_list)
        # print()
        # # print(mstSet)
        # print()

        for edge in mstSet: # for each edge in the MST Set
            for weight in mstSet[edge]: # get the weight of the source and target and add to the total weight
                total_weight += self.adj_list[edge][weight]

        return total_weight
                    

# reading from input.dat
input_dat = []

with open('input.dat', 'r') as input:
    input.readline()
    for line in input:
        input_dat.append(line.split())

# print(input_dat)

for i in input_dat:
    input_dat_edges = i[1:-1]
    input_vertex = i[-1]
    edges = [input_dat_edges[j:j+3] for j in range(len(input_dat_edges)) if j % 3 == 0]

    graph = Graph()

    for edge in edges:
        graph.addEdge(edge[0], edge[1], int(edge[2]))

    # print()
    # print(edges)
    # print()
    # print(input_vertex)
    # print(graph.adj_list)
    # print()
    print(graph.prims_algorithm(input_vertex))


# For each graph in the file, print out the total cost of all of the edges in the MST.

# for reference for in Prim's Algorthm, I read, understood and applied what is in this website:
# https://bradfieldcs.com/algos/graphs/prims-spanning-tree-algorithm/

Sample Input

2
8 A Y 5 Y X 5 X Z 5 A B 1 B C 1 B D 1 C Z 1 D Z 1 A
8 Argao Bantayan 213 Bantayan Dalaguete 230 Bantayan Cebu 146 Liloan Cebu 23 Cebu LapuLapu 19 Liloan LapuLapu 23 Dalaguete Mandaue 95 LapuLapu Mandaue 12 Cebu

Sample Output

14
508