DFS voor grafen implementeren

In deze oefening implementeer je een algoritme voor depth first search om een graaf te doorlopen.

Herinner de stappen:

Begin bij een willekeurige knoop
Voeg de knoop toe aan de lijst met bezochte knopen
Voor elke aangrenzende knoop van de huidige knoop
- Als die al bezocht is -> negeer
- Als die nog niet bezocht is -> voer recursief DFS uit

Om je code te kunnen testen, is de volgende graaf geladen met behulp van een dictionary.

Graphical representation of a graph.

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

Deze oefening maakt deel uit van de cursus

Datastructuren en algoritmen in Python

Cursus bekijken

Oefeninstructies

Controleer of current_vertex nog niet bezocht is.
Voeg current_vertex toe aan visited_vertices.
Roep dfs() recursief aan en geef de juiste waarden door.

Praktische interactieve oefening

Probeer deze oefening eens door deze voorbeeldcode in te vullen.

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')

Code bewerken en uitvoeren