Algorithmen und Datenstrukturen

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.
Video preview
Video von Reducible – Depth First Search (DFS) erklĂ€rt: Algorithmus, Beispiele und Code
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:
n = 4, e = 4
Die eingegebenen Paare a, b lauten: [(0, 1), (0, 2), (1, 2), (3, 2)]
Der Startknoten ist 3
  1. v = 3 → used = [False, False, False, True]
  1. Durchsuche alle Nachbarn von 3 ⇒ [2]
  1. v = 2 → used = [False, False, True, True]
  1. Durchsuche alle Nachbarn von 2 ⇒ [0, 1]
  1. v = 0 → used = [True, False, True, True]
  1. Durchsuche alle Nachbarn von 0 ⇒ [1, 2]
  1. v = 1 → used = [True, True, True, True]
  1. Durchsuche alle Nachbarn von 1 ⇒ [0, 2] ⇒ alle besucht
  1. ZurĂŒckkehren von 1
  1. ZurĂŒckkehren von 0
  1. ZurĂŒckkehren von 2
  1. ZurĂŒckkehren von 3 → DFS beendet
  1. Fertig
n = 5, e = 4
Die eingegebenen Paare a, b lauten: [(0, 1), (0, 2), (1, 2), (3, 4)]
Der Startknoten ist 0
  1. v = 0 → used = [True, False, False, False, False]
  1. Durchsuche alle Nachbarn von 0 ⇒ [1, 2]
  1. v = 1 → used = [True, True, False, False, False]
  1. Durchsuche alle Nachbarn von 1 ⇒ [0, 2]
  1. v = 2 → used = [True, True, True, False, False]
  1. Durchsuche alle Nachbarn von 2 ⇒ [0, 1] ⇒ alle besucht
  1. ZurĂŒckkehren von 2
  1. ZurĂŒckkehren von 1
  1. ZurĂŒckkehren von 0 → DFS beendet
  1. Fertig
      2. Notice how nodes 3 and 4 were never visited.
      They were not connected to the initial node 0.
n = 10, e = 11 (Beispiel aus dem Video)
Die eingegebenen Paare a, b lauten: [(0, 1), (0, 2), (1, 2), (1, 4), (1, 3), (3, 5), (6, 5), (5, 8), (5, 7), (7, 8), (8, 9)]
Der Startknoten ist 0
  1. v = 0 → used = [T, F, F, F, F, F, F, F, F, F] ⇒ erkunde [1, 2]
  1. v = 1 → used = [T, T, F, F, F, F, F, F, F, F] ⇒ erkunde [0, 2, 3, 4]
  1. v = 2 → used = [T, T, T, F, F, F, F, F, F, F] ⇒ erkunde [0, 1]
  1. ZurĂŒckkehren von 2
  1. v = 1 → used = [T, T, T, F, F, F, F, F, F, F] ⇒ erkunde [x, x, 3, 4]
  1. v = 3 → used = [T, T, T, T, F, F, F, F, F, F] ⇒ erkunde [1, 5]
  1. v = 5 → used = [T, T, T, T, F, T, F, F, F, F] ⇒ erkunde [3, 6, 7, 8]
  1. v = 6 → used = [T, T, T, T, F, T, T, F, F, F] ⇒ erkunde [5]
  1. ZurĂŒckkehren von 6
  1. v = 7 → used = [T, T, T, T, F, T, T, T, F, F] ⇒ erkunde [5, 8]
  1. v = 8 → used = [T, T, T, T, F, T, T, T, T, F] ⇒ erkunde [5, 7, 9]
  1. v = 9 → used = [T, T, T, T, F, T, T, T, T, T] ⇒ erkunde [8]
  1. ZurĂŒckkehren von 8
  1. ZurĂŒckkehren von 7
  1. ZurĂŒckkehren von 6
  1. ZurĂŒckkehren von 5
  1. ZurĂŒckkehren von 3
  1. v = 1 → used = [T, T, T, T, F, T, T, T, T, T] ⇒ erkunde [x, x, x, 4]
  1. v = 4 → used = [T, T, T, T, T, T, T, T, T, T] ⇒ erkunde [1]
  1. ZurĂŒckkehren von 4
  1. ZurĂŒckkehren von 1
  1. ZurĂŒckkehren von 0
  1. Fertig
 

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

Eingabe
Ausgabe
7 6 1 2 2 3 1 3 4 5 5 6 4 6
3
2 1 1 2
1
2 0
2
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue