Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.

Below algorithm presents the steps for graph traversal using DFS:

**Algorithm DFS(v);**

**Input**: A vertex v in a graph

**Output**: A labeling of the edges as “discovery” edges
and “backedges”

```
for each edge e incident on v do
if edge e is unexplored then
let w be the other endpoint of e
if vertex w is unexplored then
label e as a discovery edge
recursively call DFS(w)
else
label e as a backedge
```

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow