Algorithmus: Breadth First Search (BFS)
Stellen Sie sich vor, Sie haben einen Graphen mit
n Knoten und e Kanten. Von einem Startknoten aus möchten Sie Schritt für Schritt alle erreichbaren Knoten im Graphen besuchen. Es gibt verschiedene Methoden, dies zu tun, und eine der bekanntesten ist der BFS (Breadth-First Search) Algorithmus. Aufgrund seiner Vorgehensweise kann BFS den kürzesten Weg vom Startknoten zu sämtlichen anderen Knoten im Graphen ermitteln – was ihn in vielen Anwendungen äußerst hilfreich macht.
Eine anschauliche Art, sich den BFS-Algorithmus vorzustellen, ist das Bild eines brennenden Graphen, in dem sich das Feuer nach und nach ausbreitet. Jeder Knoten brennt 1 Minute und entzündet danach seine direkten Nachbarn, die wiederum 1 Minute brennen, bevor sie ihrerseits ihre Nachbarn entzünden usw.
Zunächst “zünden” Sie den Startknoten an. Dann breitet sich das Feuer auf alle seine Nachbarn aus. Nach einer Minute beginnen deren Nachbarn zu brennen und geben das Feuer wiederum weiter. Dieser Prozess geht weiter, bis alle erreichbaren Knoten abgebrannt sind. Diese Vorstellung eines sich ausbreitenden Feuers hilft enorm bei der Umsetzung des BFS.
Die Implementierung des BFS lässt sich gut mithilfe einer
queue (Warteschlange) und einer Liste von “benutzten” (besuchten) Knoten used realisieren:from collections import deque
n, e = map(int, input().split()) # n: Knoten, e: Kanten
g = [[] for _ in range(n)] # Graph - Adjazenzliste
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)
start = int(input()) # Startknoten
used = [False] * n # benutzte (besuchte) Knoten
q = deque([start]) # Warteschlange mit Startknoten
used[start] = True # Startknoten als besucht markieren
while q: # solange die Warteschlange nicht leer ist
v = q.popleft() # Knoten aus der Warteschlange nehmen
print(v, end=' ') # Knoten ausgeben
for to in g[v]: # für alle Nachbarn dieses Knotens
if not used[to]: # wenn ein Nachbar noch nicht besucht wurde
q.append(to) # Nachbar zur Warteschlange hinzufügen
used[to] = True # Nachbar als besucht markierenZuerst wird der Graph initialisiert, und die Graphdurchquerung startet beim Knoten
start. Anfangs sind alle Einträge in used auf False gesetzt. Sobald ein Knoten besucht wird, landet er in der Warteschlange und wird als verwendet (brennend) markiert. In jedem Schritt fügen wir alle unbesuchten Nachbarn des Knotens v aus dem Graphen zur Warteschlange hinzu und markieren sie als besucht.Werfen wir einen Blick darauf, wie der Algorithmus auf verschiedenen Eingaben funktioniert:
n = 4, e = 4
Die Eingabe „a, b“ Paare lauten: [(0, 1), (0, 2), (1, 2), (3, 2)]
Der Startknoten ist 3
used = [False, False, False, True],q = [3]
v = 3,q = []→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
used = [False, False, True, True],q = [2]
v = 2,q = []→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
used = [True, True, True, True],q = [0, 1]
v = 0,q = [1]→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
v = 1,q = []→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
- Ende
n = 5, e = 4
Die Eingabe „a, b“ Paare lauten: [(0, 1), (0, 2), (1, 2), (3, 4)]
Der Startknoten ist 0
used = [True, False, False, False, False],q = [0]
v = 0,q = []→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
used = [True, True, True, False, False],q = [1, 2]
v = 1,q = [2]→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
v = 2,q = []→ Alle unbesuchten Nachbarn werden zur Warteschlange hinzugefügt
- Ende
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Aufgabe: Zählen Sie die Anzahl der Zusammenhangskomponenten in einem Graphen
Angenommen, Sie haben einen ungerichteten Graphen mit
v Knoten und e Kanten. Ihre Aufgabe besteht darin, die Anzahl der Zusammenhangskomponenten in diesem Graphen zu ermitteln. Eine Gruppe von Knoten gilt als Zusammenhangskomponente, wenn man zwischen ihnen hin- und herwandern 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 Paare von ganzen Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Damit wird angegeben, dass Knoten v1 mit Knoten v2 verbunden ist (und umgekehrt).Ausgabe
Ihr Programm soll die Anzahl der Zusammenhangskomponenten im 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: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB