- Most graph problems involve traversal of a graph. Traversal of a graph means visit each node exactly once.
- Two commonly used graphs traversal techniques are
- Depth First Search (DFS)
- Breadth First Search (BFS)
Depth First Search (DFS)
- It is like preorder traversal of tree.
- Traversal can start from any vertex vi
- Vi is visited and then all vertices adjacent to vi are traversed recursively using DFS
DFS(G,1) is given by
a) Visit(1)
b) DFS(G,2)
DFS(G,3)
DFS(G,4)
DFS(G,5)
DFS traversal of given graph is: 1, 2, 6, 3, 8, 7, 4, 5
Since graph can have cycles, we must avoid re-visiting a node. To do this when we visit a vertex V, we marks it visited as visited should not be selected for traversal.
