Algorithms For Dummies

CONSIDERING REDUNDANCY

When traversing a tree, every path ends in a leaf node so that you know that you have 

reached the end of that path. However, when working with a graph, the nodes intercon-

nect such that you might have to traverse some nodes more than once to explore the 

entire graph. As the graph becomes denser, the possibility of visiting the same node 

more than once increases. Dense graphs can greatly increase both computational and 

storage requirements.

To reduce the negative effects of visiting a node more than once, it’s common to mark 

each visited node in some manner to show that the algorithm has visited it. When the 

algorithm detects that it has visited a particular node, it can simply skip that node and 

move onto the next node in the path. Marking visited nodes decreases the performance 

penalties inherent in redundancy.

Marking visited nodes also enables verification that the search is complete. Otherwise, 

an algorithm can end up in a loop and continue to make the rounds through the graph 

indefinitely.

---

CHAPTER 9