Graph traversal: Difference between revisions

Revision as of 17:21, 25 December 2019

Revision as of 17:22, 25 December 2019

Line 29:

* ''Output'': A labeling of the edges in the connected component of ''v'' as discovery edges and back edges.

1 '''procedure''' DFS(''G'', ''v''): '''is'''

2 label ''v'' as explored

3 '''for all''' edges ''e'' in ''G''.incidentEdges(''v'') '''do'''

4 '''if''' edge ''e'' is unexplored '''then'''

5 ''w'' ← ''G''.adjacentVertex(''v'', ''e'')

6 '''if''' vertex ''w'' is unexplored '''then'''

7 label ''e'' as a discovered edge

8 recursively call DFS(''G'', ''w'')

9 '''else'''

10 label ''e'' as a back edge

===Breadth-first search===