What are Graphs? – Part 5 Prim

Hi, in the fifth part of my graph series, I want to talk about the Prim algorithm. In the fourth part, we programmed the breadth-first search in Python.

Now it's time for Prim. What is Prim? Prim is a greedy algorithm, which tries to take the edge with the least weight at a node in the graph. However, this is no guarantee that all paths have the least effort. Prim creates a minimum spanning tree from the graph, which consists of all the nodes that could be reached and edges with low effort. Before we continue, let's look at the graph again.

As mentioned, Prim is a greedy algorithm. Prim searches for the shortest paths and connects all nodes it can reach to a Minimum Spanning Tree (MST). What is meant by "the ones it can reach"? Prim goes from node to node, which means if nodes in the graph are not connected to any other nodes, or the graph is not fully connected, Prim cannot reach them. So with Prim, the graph must be connected so that every node is reachable.

How does Prim work?

Prim starts at a random or selected node. Prim determines all edges or neighboring nodes and places them in a queue. When Prim has determined all neighbors at the node, Prim takes the neighboring node that can be reached with little effort or distance. He then adds the nodes to the MST. Here Prim must take care that he does not connect any nodes with each other, which generate a cycle. That means it must not be the case that $A$ points to $B$, $B points to$C$and$C$points again to$A$. Prim does the whole game until the tree is finished or the queue is empty.

A small animation illustrates the process of Prim.

The blue markers are the visits of the nodes. Purple represents the determinations.

Extend our graph implementation

Now we extend our class Graph with Prim. I have implemented this iteratively here. Additionally I wrote a helper function, which always finds the minimum in the list.

def __min(self, q):
    _min = None
    for entry in q:
        if _min == None:
            _min = entry

        elif entry[1] < _min[1]:
            _min = entry

    return _min

The method min, outputs the smallest edge from the passed list. This is called by Prim.

def prim(self, key):
    cost = 0.0
    mst = []
    self.unvisitAllNodes()
    n = self.getNode(key)
    q = [(n, 0)]
    n.visit()
    while len(q) != 0:
        entry = self.__min(q)
        q.remove(entry)
        current = entry[0]
current.visit()
        for edge in current.getEdges():
            if not edge.getB().isVisited():
                edge.getB().visit()
                mst.append([current.getKey(), edge.getWeight(), edge.getB().getKey()])
                q.append((edge.getB(), edge.getWeight()))
                cost += edge.getWeight()

    print("MST:", mst)
    print("Total cost", cost)

Here in the method Prim is implemented. Here all nodes ls not visited are marked and the total cost is initialized. The starting node is selected and added to the list q, which represents our PriorityQueue. Now the queue is processed until it is empty. Each time the smallest edge is taken from the queue and visited. Its neighboring nodes are determined and checked which of them have not yet been visited. These are then added to the queue. Each node that was visited for the first time is added to the MST. Here the MST is a list mst.

In the end, if we let the whole thing run, you should get an MST. Output Start Node A :

PRIM MST
A ---> B weight: 1.0
A ---> D weight: 1.4
B ---> C weight: 4.8
D ---> E weight: 2.4
D ---> F weight: 2.6
MST: [['A', 1.0, 'B'], ['A', 1.4, 'D'], ['B', 4.8, 'C'], ['D', 2.4, 'E'], ['D', 2.6, 'F']]
Total cost 12.2

I hope I could explain Prim to someone 😄