Algorithms For Dummies

Sorting the Graph Elements

The ability to search graphs efficiently relies on sorting. After all, imagine going 

to a library and finding the books placed in any order the library felt like put-

 ting them on the shelves. Locating a single book would take hours. A library  

works because the individual books appear in specific locations that make them 

easy to find.

Libraries also exhibit another property that’s important when working with cer-

tain kinds of graphs. When performing a book search, you begin with a specific 

category, then a row of books, then a shelf in that row, and finally the book. You 

move  from  less  specific  to  more  specific  when  performing  the  search,  which 

means that you don’t revisit the previous levels. Therefore, you don’t end up in 

odd parts of the library that have nothing to do with the topic at hand.