Errata for Problem Solving with Algorithms and Data Structures using Python

Chapter 1 - Introduction

Chapter 2 - Stacks and Queues

Chapter 3 - Recursion

Chapter 4 - Analysis, Sorting, and Searching

Chapter 5 - Trees

Chapter 6 - Graphs

Listing 6.9

Although the dfs algorithm in the text works fine, the following recursive version of DFS is more appropriate for use with the topological sort.

00001: # DFS implementation using adjGraph where nodes contain an adj list reference to other nodes
00002: 
00003: time = 0
00004: 
00005: def dfs(theGraph):
00006:     for u in theGraph:
00007:         u.setColor('white')
00008:         u.setPred(-1)
00009:     time = 0
00010:     for u in theGraph:
00011:         if u.getColor() == 'white':
00012:             dfsiter(u)
00013: 
00014: def dfsvisit(u):
00015:     global time
00016:     u.setColor('gray')
00017:     time = time+1
00018:     u.setDiscovery(time)
00019:     for v in u.getAdj():
00020:         if v.getColor() == 'white':
00021:             v.setPred(u)
00022:             dfsvisit(v)
00023:     u.setColor('black')
00024:     time = time + 1
00025:     u.setFinish(time)
00026: 

Page 264, Step 2 in Topological sort: Order the list of vertices in decreasing order of finish time

Listing 6.11

The version of Prim's algorithm in listing 6.11 contains typos

00001: def prim(G,w,start):
00002:     PQ = PriorityQueue()
00003:     for v in G:
00004:         v.setDistance(sys.maxint)
00005:         v.setPred(None)
00006:     start.setDistance(0)
00007:     PQ.buildHeap([(v.getDistance(),v) for v in G])
00008:     while not PQ.isEmpty():
00009:         u = PQ.delMin()
00010:         for v in u.getAdj():
00011:             if v in PQ and u.getCost(v) < v.getDistance():
00012:                 if v.getPred() != None:
00013:                     G.findEdge(v,v.getPred()).remove()
00014:                 v.setPred(u)
00015:                 v.setDistance(u.getCost(v))
00016:                 PQ.decreaseKey(v,u.getCost(v))

Chapter 7