1. Learn
    2. /
  2. Courses
    3. /
  3. Data Structures and Algorithms in Python
Connected

Exercise

Implementing DFS for graphs

In this exercise, you will implement a depth first search algorithm to traverse a graph.

Recall the steps:

  1. Start at any vertex
  2. Add the vertex to the visited vertices list
  3. For each current node's adjacent vertex
    • If it has been visited -> ignore it
    • If it hasn't been visited -> recursively perform DFS

To help you test your code, the following graph has been loaded using a dictionary.

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

Instructions

100 XP
  • Check if current_vertex hasn't been visited yet.
  • Add current_vertex to visited_vertices.
  • Call dfs() recursively by passing it the appropriate values.