Algorithmus in Python (Breitenprioritätssuche, bfs)

Einführung

Ich werde die Implementierung der Suche nach Breitenpriorität mit Python erklären. (Setzen Sie einfach die ein, die ich immer implementiere.) Die Suche mit der Breite und Priorität wirft häufig das Problem der Entfernung auf. Daher implementieren wir dieses Mal eine Funktion, die die Entfernung von einem Scheitelpunkt zu jedem Scheitelpunkt zurückgibt.

Suche nach Breitenpriorität

Ich denke, dass eine Menge allgemeines Wissen über die Suche nach Breitenprioritäten herauskommt, wenn Sie es nachschlagen. Ich werde es daher im Detail weglassen, aber ich werde es kurz erklären. 　　　 Folgen Sie, wie durch den blauen Pfeil dargestellt, den Scheitelpunkten in der Reihenfolge vom nächsten. Bei der diesmal zu behandelnden Entfernung addieren Sie 1 zur Entfernung zum vorherigen Scheitelpunkt. (Im Bild wird es von 1 geschüttelt, aber wenn es eine Entfernung ist, kann es von 0 geschüttelt werden.) Die Reihenfolge der Suche nach diesem Scheitelpunkt wird von der Warteschlange verwaltet. Eine Warteschlange ist eine First-In- und First-Out-Datenstruktur. In diesem Beispiel wird zuerst der Start 0 eingegeben. ([0]) Nehmen Sie als nächstes den Inhalt von vorne heraus und untersuchen Sie die benachbarten Eckpunkte. (Diesmal 1 und 2) Wenn Sie zum ersten Mal hier sind, fügen Sie es der Warteschlange hinzu. ([1, 2]) Wenn Sie dies wiederholen, können Sie die Eckpunkte in der Reihenfolge der blauen Pfeile untersuchen. （[2, 3, 4]→[3, 4, 5, 6]→[4, 5, 6, 7]...） Die Suche endet, wenn die Warteschlange leer ist. Ist Prost auf gute Arbeit.

Implementierung

Eingang

Wenn die Anzahl der Eckpunkte n und die Anzahl der Seiten m gegeben sind, werden benachbarte Eckpunkte über m Reihen gegeben.

11 9
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5 8
8 9

Code

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()] #n ist die Anzahl der Eckpunkte, m ist die Anzahl der Seiten
g = [[] for _ in range(n)] #Benachbarte Liste

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n #Initialisierung der Entfernung von u
    d[u] = 0 #Entfernung zu mir ist 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

#Abstand jedes Scheitelpunkts von 0
d = bfs(0)
print(d)

Ausgabe

Gibt eine Liste mit dem Abstand vom Scheitelpunkt 0 in der Reihenfolge der Scheitelpunktnummer von links aus. Die Entfernung zu sich selbst beträgt 0, und die Spitzen, die Sie nicht erreichen können, sind Keine.

[0, 1, 1, 2, 2, 2, 2, 3, 3, 4, None]

abschließend

Bitte lassen Sie mich wissen, wenn Sie Fehler haben! Ich wäre Ihnen dankbar, wenn Sie mir einen Rat geben könnten!