Algorithms For Dummies

 Exploring the World of Graphs

2. 

Start from any vertex in the graph and place it into the solution.

3. 

Determine whether there are still vertexes that aren’t part of the solution:

• 

Enumerate the edges that touch the vertexes in the solution.

• 

Insert the edge with the minimum weight into the spanning tree. (This is 

the greedy principle at work in the algorithm: Always choose the minimum 

at each step to obtain an overall minimum result.)

By translating these steps into Python code, you can test the algorithm on the 

example weighted graph using the following code:

def prim(graph, start):

    treepath = {}

    total = 0

    queue = priority_queue()

    queue.push(0 , (start, start))

    while queue:

        weight, (node_start, node_end) = queue.pop()

        if node_end not in treepath:

            treepath[node_end] = node_start

            if weight:

                print("Added edge from %s" \

                      " to %s weighting %i"

                      % (node_start, node_end, weight))

                total 

+= weight

            for next_node, weight \

            in graph[node_end].items():

                queue.push(weight , (node_end, next_node))

    print ("Total spanning tree length: %i" % total)

    return treepath

treepath = prim(graph, 'A')

Added edge from A to B weighting 2

Added edge from B to C weighting 2

Added edge from B to D weighting 2

Added edge from D to E weighting 1

Added edge from E to F weighting 1

Total spanning tree length: 8

The algorithm prints the processing steps, showing the edge it adds at each stage 

and the weight the edge adds to the total. The example displays the total sum of 

weights and the algorithm returns a Python dictionary containing the ending 

vertex as key and the starting vertex as value for each edge of the resulting 

---

CHAPTER 9