Graph Traversal - Redundancy

Redundancy

Unlike tree traversal, graph traversal may require that some nodes be visited more than once, since it is not necessarily known before transitioning to a node that it has already been explored. As graphs become more dense, this redundancy becomes more prevalent, causing computation time to increase; as graphs become more sparse, the opposite holds true.

Thus, it is usually necessary to remember which nodes have already been explored by the algorithm, so that nodes are revisited as infrequently as possible (or in the worst case, to prevent the traversal from continuing indefinitely). This may be accomplished by associating each node of the graph with a "color" or "visitation" state during the traversal, which is then checked and updated as the algorithm visits each node. If the node has already been visited, it is ignored and the path is pursued no further; otherwise, the algorithm checks/updates the node and continues down its current path.

Several special cases of graphs imply the visitation of other nodes in their structure, and thus do not require that visitation be explicitly recorded during the traversal. An important example of this is a tree, during a traversal of which it may be assumed that all "ancestor" nodes of the current node (and others depending on the algorithm) have already been visited. Both the depth-first and breadth-first graph searches are adaptations of tree-based algorithms, distinguished primarily by the lack of a structurally determined "root" node and the addition of a data structure to record the traversal's visitation state.