Graph traversal: Difference between revisions

Revision as of 10:57, 9 May 2017

Revision as of 20:17, 11 July 2017

Line 6:

==Redundancy==

Unlike tree traversal, graph traversal may require that some vertices be visited more than once, since it is not necessarily known before transitioning toljuualto a vertex that it has already been explored. As graphs become more [[dense graph|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 vertices have already been explored by the algorithm, so that vertices 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 vertex of the graph with a "color" or "visitation" state during the traversal, which is then checked and updated as the algorithm visits each vertex. If the vertex has already been visited, it is ignored and the path is pursued no further; otherwise, the algorithm checks/updates the vertex and continues down its current path.