Data Structure (2130702)

• 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.

Breadth First Search (BFS)

• This methods starts from vertex V₀.
• V0 is marked as visited. All vertices adjacent to V₀ are visited next.
• Let vertices adjacent to V₀ are V₁, V₂, V₃, V₄.
• V₁, V₂, V₃ and V₄ are marked visited.
• All unvisited vertices adjacent to V₁, V₂, V₃, V₄ are visited next.
• The method continuous until all vertices are visited.
• The algorithm for BFS has to maintain a list of vertices which have been visited but not explored for adjacent vertices. The vertices which have been visited but not explored for adjacent vertices can be stored in queue.
• Initially the queue contains the starting vertex.
• In every iteration, a vertex is removed from the queue and its adjacent vertices which are not visited as yet are added to the queue.
• The algorithm terminates when the queue becomes empty.