Tiefensuche (Depth First Search, DFS)

Stellen Sie sich vor, Sie steuern einen Roboter, der sich an einem bestimmten Ort in einem Graphen mit n Knoten und e Kanten befindet. Sie möchten von einem Startknoten aus nach und nach den gesamten Graphen erkunden und alle erreichbaren Knoten besuchen. Der DFS-Algorithmus macht genau das, indem er von einem Startknoten aus einen Pfad so weit wie möglich verfolgt. Sobald es dort keine neuen Knoten mehr gibt, geht er auf die vorherigen Knoten zurück und sucht von dort neue, noch nicht besuchte Wege.

Eine hilfreiche Vorstellung für den DFS-Algorithmus ist die Idee eines Roboters, der von Knoten zu Knoten geht. Er kann nur die Nachbarn des aktuellen Knotens und jene Knoten sehen, die er schon besucht hat (er behält also den gesamten Weg im Blick). Dieses Vorgehen ist ein rekursiver Prozess: In jedem Schritt bewegt sich der Roboter zu einem bisher unbesuchten Knoten und wiederholt das Vorgehen, bis kein weiterer unentdeckter Knoten mehr auf diesem Pfad liegt. Wenn man sich das als kleinen Roboter vorstellt, ist die Umsetzung oft einfacher.

Die Implementierung des DFS-Algorithmus kann mithilfe einer rekursiven Funktion umgesetzt werden. Dabei behalten wir den aktuellen Knoten (den wir mit v bezeichnen) und alle bereits besuchten Knoten (in used) im Blick:

import sys

sys.setrecursionlimit(10 ** 6)          # Erhöht das Rekursionslimit, damit DFS korrekt ausgeführt werden kann

n, e = map(int, input().split())        # n: Knoten, e: Kanten
g = [[] for _ in range(n)]              # Graph - Adjazenzliste
used = [False] * n                      # bereits besuchte Knoten

for _ in range(e):                      # Kanten einlesen
    a, b = map(int, input().split())    # a -> b und b -> a
    g[a].append(b)
    g[b].append(a)


def dfs(v):                             # Tiefensuche
    used[v] = True                      # Knoten als besucht markieren
    print(v, end=' ')                   # Knoten ausgeben
    for to in g[v]:                     # für jeden mit v verbundenen Knoten
        if not used[to]:                # falls Knoten noch nicht besucht
            dfs(to)                     # DFS für diesen Knoten aufrufen


start = int(input())                    # Startknoten einlesen
dfs(start)                              # DFS vom Startknoten aus aufrufen

Zunächst initialisieren wir also den Graphen und beginnen die Traversierung beim Knoten start. Alle Werte in used sind anfangs False. Sobald wir einen Knoten besuchen, setzen wir ihn mit used[v] = True auf besucht und gehen dann alle Nachbarn des aktuellen Knotens v durch.

Die Rekursion übernimmt dabei die Rolle, den Weg zu erkunden. Sobald ein Pfad erschöpft ist, „kehrt“ die Funktion zur vorherigen Position zurück, um von dort aus die übrigen Nachbarn zu durchsuchen. Wenn wir uns mit der Rückkehr aus der Rekursion gedanklich wieder zum Knoten davor „bewegen“, verstehen wir leicht, wie der Algorithmus arbeitet.

Werfen wir einen Blick auf einige Eingaben und deren Abläufe:

Herausforderung: Anzahl der zusammenhängenden Komponenten zählen

Gegeben ist ein ungerichteter Graph mit v Knoten und e Kanten. Ihre Aufgabe ist es, die Anzahl der zusammenhängenden Komponenten dieses Graphen zu bestimmen. Eine Menge von Knoten gilt als eine zusammenhängende Komponente, wenn man innerhalb dieser Menge von jedem Knoten jeden anderen Knoten erreichen kann.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).

Die folgenden e Zeilen enthalten jeweils ein Paar Ganzzahlen v1, v2 (1 ≤ v1, v2 ≤ v). Dies bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.

Ausgabe

Das Programm soll die Anzahl der zusammenhängenden Komponenten des Graphen ausgeben.

Beispiele