Data Structure (2130702)

BE | Semester-3   Summer-2019 | 06/04/2019

Q3) (b)

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
    1. Depth First Search (DFS)
    2. 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.
Depth First Search (DFS) example