Implementing DFS for graphs

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

Recall the steps:

Start at any vertex
Add the vertex to the visited vertices list
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']
}

This exercise is part of the course

Data Structures and Algorithms in Python

View Course

Exercise instructions

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

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

def dfs(visited_vertices, graph, current_vertex):
    # Check if current_vertex hasn't been visited yet
    if current_vertex not in ____:
        print(current_vertex)
        # Add current_vertex to visited_vertices
        ____.add(____)
        for adjacent_vertex in graph[current_vertex]:
            # Call recursively with the appropriate values
            ____(____, ____, ____)
            
dfs(set(), graph, '0')

Edit and Run Code