Errata and Clarifications

Chapter Index, page 672-681, Index

Contributor(s): Michael Goodrich

The index printed in the book was erroneously constructed using an old data file. Please replace it with this revised Index (in PDF).

Chapter 7, page 309, Code Fragment 7.3

Contributor(s): Michael Goodrich

Replace

represeting

with

representing

Chapter 7, page 312, Code Fragment 7.5

Contributor(s): Michael Goodrich

In the condition for second while loop, replace

!S.isEmpty()

with

!P.isEmpty()

Chapter 12, page 656, Exercise C-12.28

Contributor(s): Wim H. Hesselink

The pseudo-code for Baruvka's algorithm is correct only for graphs with unique edge weights. Incidentally, if the edge weights in G are not initially unique, we can impose uniqueness by numbering the vertices 1 to n and taking the new weight of each edge e=(u,v), written so that u is numbered less than v, to be (w(e),u,v), where w(e) is the old weight of e and we use a lexicographic comparator for the new weights.