Implementierung von DFS für Graphen

In dieser Übung implementierst du einen Algorithmus zur Tiefensuche, um einen Graphen zu durchlaufen.

Erinnere dich an die Schritte:

Start an einem beliebigen Scheitelpunkt
Den Punkt zur Liste der besuchten Punkte hinzufügen
Für jeden benachbarten Knotenpunkt des aktuellen Knotens
- Wenn es bereits besucht wurde -> ignoriere es
- Wenn es noch nicht besucht wurde -> rekursiv ausführen DFS

Damit du deinen Code testen kannst, wurde die folgende Grafik mit einem Wörterbuch geladen.

Grafische Darstellung eines Diagramms.

graph = {

  '0' : ['1','2'],

  '1' : ['0', '2', '3'],

  '2' : ['0', '1', '4'],

  '3' : ['1', '4'],

  '4' : ['2', '3']

}

Diese Übung ist Teil des Kurses

Datenstrukturen und Algorithmen in Python

Kurs anzeigen

Anleitung zur Übung

Prüfe, ob current_vertex noch nicht besucht wurde.
Füge current_vertex zu visited_vertices hinzu.
Rufe dfs() rekursiv auf, indem du ihm die entsprechenden Werte übergibst.

Interaktive Übung

Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.

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 bearbeiten und ausführen