Algorithms For Dummies

a.  Choose the shortest edge from the heap.

b.  Determine whether the two vertexes connected by the edge appear in 

different trees from among the set of connected trees.

---

190

 

   

  PART 3 

 Exploring the World of Graphs

c.  When the trees differ, connect the trees using the edge (defining an 

aggregation).

d.  When the vertexes appear in the same tree, discard the edge.

e.  Repeat steps a through d for the remaining edges on the heap.

The following example demonstrates how to turn these steps into Python code:

def kruskal(graph):

    priority = priority_queue()

    print ("Pushing all edges into the priority queue")

    treepath = list()

    connected = dict()

    for node in graph:

        connected[node] = [node]

        for dest, weight in graph[node].items():

            priority.push(weight, (node,dest))

    print ("Totally %i edges" % len(priority))

    print ("Connected components: %s"

           % connected.values())

    total = 0

    while len(treepath) < (len(graph)-1):

        (weight, (start, end)) = priority.pop()

        if end not in connected[start]:

            treepath.append((start, end))

            print ("Summing %s and %s components:"

                   % (connected[start],connected[end]))

            print ("\tadded edge from %s " \

                   "to %s weighting %i"

                   % (start, end, weight))

            total 

+= weight

            connected[start] 

+= connected[end][:]

            for element in connected[end]:

                connected[element]= connected[start]

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

    return sorted(treepath, key=lambda x:x[0])

print ('\nMinimum spanning tree: %s' % kruskal(graph))

Pushing all edges into the priority queue

Totally 9 edges

Connected components: dict_values([['A'], ['E'], ['F'],

                                  ['B'], ['D'], ['C']])

---

CHAPTER 9