Implementera DFS för grafer

I den här övningen implementerar du en djupet-först-sökning (depth first search) för att traversera en graf.

Kom ihåg stegen:

Börja i valfritt hörn
Lägg till hörnet i listan över besökta hörn
För varje angränsande hörn till den aktuella noden
- Om det redan har besökts -> ignorera det
- Om det inte har besökts -> utför DFS rekursivt

För att hjälpa dig testa koden har följande graf laddats in med hjälp av en ordlista.

Grafisk representation av en graf.

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

Den här övningen är en del av kursen

Datastrukturer och algoritmer i Python

Visa kurs

Övningsinstruktioner

Kontrollera om current_vertex inte har besökts än.
Lägg till current_vertex i visited_vertices.
Anropa dfs() rekursivt och skicka med rätt värden.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

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

Redigera och kör kod