List out graph traversal techniques & explain any one using suitable example.
- 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.
- 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.
