Ich habe gehört, dass es bei der Suche nach Tiefenpriorität mit Python ein Leistungsproblem mit rekursiv gibt, daher habe ich beschlossen, es mit Stack zu implementieren, und es als Memorandum im Artikel belassen. Ich hoffe es hilft dir beim Lernen und wenn du einen Rat hast, hinterlasse bitte einen Kommentar!
Dieses Mal werden wir die Zeit berücksichtigen, die benötigt wird, um einen bestimmten Scheitelpunkt zu starten und jeden Peak zu erreichen. Dies ist ein typisches Thema bei der Suche nach Tiefenprioritäten. (Ist es eher eine Bestellung als eine Zeit?) Überprüfen Sie zu diesem Zeitpunkt die Ankunftszeit ** gehende Bestellung **, überprüfen Sie die letzte verstrichene Zeit ** Rücksendung ** und notieren Sie beide zusammen mit ** Zeitstempel **. Wir werden uns mit den drei Fällen befassen. Der letzte Durchgang erfolgt unmittelbar nach Abschluss der Suche nach allen Scheitelpunkten unterhalb dieses Scheitelpunkts. Ich werde nicht näher auf dfs eingehen, aber ich werde vom Ausgangspunkt bis zu meinem Ziel tiefer gehen, und wenn ich nicht weiter gehen kann, werde ich zur vorherigen Gabelung zurückkehren und dasselbe wiederholen. Nehmen wir hier an, dass derjenige mit der jüngeren Scheitelpunktnummer bevorzugt gesucht wird.
Geben Sie die Anzahl der Scheitelpunkte in der ersten Zeile als Ganzzahl ein und geben Sie dann die Scheitelpunktnummer, die Anzahl benachbarter Scheitelpunkte und die benachbarten Scheitelpunkte in der N-Linie ein, die durch Leerzeichen getrennt sind.
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0
Die Scheitelpunktnummer, die Ankunftszeit und die Suchendzeit werden in Zeile N ausgegeben, die durch Leerzeichen getrennt sind. (Nur der erstere ist in der Reihenfolge des Gehens und nur der letztere ist in der Reihenfolge der Rückkehr.)
1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6
dfs_1.py
#Tiefenprioritätssuche (los)
import sys
input = sys.stdin.readline
from collections import deque
#Diagramm erstellen(In der ungerichteten Grafik#Löschen)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
u, k, * v = [int(x) for x in input().split()] #u ist die Scheitelpunktnummer und k ist die Anzahl benachbarter Scheitelpunkte
v.sort()
for i in v:
graph[u].append(i)
# graph[i].append(u) #Ungerichtete Grafik
time = 0
arrive_time = [-1] * (N + 1) #Ankunftszeit
#Tiefenprioritätssuche
def dfs(v):
global time
time += 1
stack = [v]
arrive_time[v] = time
while stack:
v = stack[-1]
if graph[v]:
w = graph[v].popleft()
if arrive_time[w] < 0:
time += 1
arrive_time[w] = time
stack.append(w)
else:
stack.pop()
return arrive_time
#Isolierte Apex-Maßnahmen
for i in range(N):
if arrive_time[i + 1] < 0:
ans = dfs(i + 1)
#Spitzenzahl, Ankunftszeit
for j in range(N):
temp = [j + 1, ans[j + 1]]
print(* temp)
Zunächst wird der Graph durch eine Adjazenzliste dargestellt. Hier wird es als gerichteter Graph betrachtet, aber es kann auch als ungerichteter Graph behandelt werden, indem ein # im Code entfernt wird. Die Zeit kann als globale Variable auf einer gemeinsamen Zeitachse behandelt werden, unabhängig davon, welcher Scheitelpunkt aufgerufen wird. Wenn ein neuer Scheitelpunkt erreicht wird, wird er um +1 erhöht und in der Ankunftszeit-Ankunftszeitliste aufgezeichnet. Einige gerichtete Graphen können vom Startpeak aus nicht erreicht werden. Wenn also nicht alle Peaks erreicht wurden, wird eine Suche mit Tiefenpriorität durchgeführt. Da der Stapel Last-In-First-Out ist, wird das hintere Element herausgenommen und die benachbarten Eckpunkte werden untersucht. Entfernen Sie diese Scheitelpunkte aus der Adjazenzliste, damit Sie sehen können, was Sie untersucht haben. Wenn der Inhalt leer ist, ist die Suche nach dem Scheitelpunkt abgeschlossen. Löschen Sie ihn daher vom Stapel.
dfs_2.py
#Suche nach Tiefenpriorität (Rückkehr)
import sys
input = sys.stdin.readline
from collections import deque
#Diagramm erstellen(In der ungerichteten Grafik#Löschen)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
u, k, * v = [int(x) for x in input().split()] #u ist die Scheitelpunktnummer und k ist die Anzahl benachbarter Scheitelpunkte
v.sort()
for i in v:
graph[u].append(i)
# graph[i].append(u) #Ungerichtete Grafik
time = 0
arrive = [-1] * (N + 1) #Bist du angekommen
finish_time = [-1] * (N + 1) #Suche Endzeit
#Tiefenprioritätssuche
def dfs(v):
global time
stack = [v]
arrive[v] = 1
while stack:
v = stack[-1]
if graph[v]:
w = graph[v].popleft()
if arrive[w] < 0:
arrive[w] = 1
stack.append(w)
else:
time += 1
finish_time[v] = time
stack.pop()
return finish_time
#Isolierte Apex-Maßnahmen
for i in range(N):
if arrive[i + 1] < 0:
ans = dfs(i + 1)
#Boxennummer, Endzeit
for j in range(N):
temp = [j + 1, ans[j + 1]]
print(* temp)
Die verwendeten Variablen und Ideen sind fast gleich, aber dieses Mal werden wir die Zeit aufzeichnen, zu der die Suche in finish_time endete, nicht die Zeit, als sie ankam. Mit anderen Worten, wenn ein benachbarter Scheitelpunkt eines bestimmten Scheitelpunkts aus der Adjazenzliste gelöscht wird, wenn er leer wird, rückt die Zeit vor und die Zeit wird aufgezeichnet.
dfs_3.py
#Suche nach Tiefenpriorität (gehen, zurückkehren)
import sys
input = sys.stdin.readline
from collections import deque
#Diagramm erstellen(In der ungerichteten Grafik#Löschen)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
u, k, * v = [int(x) for x in input().split()] #u ist die Scheitelpunktnummer und k ist die Anzahl benachbarter Scheitelpunkte
v.sort()
for i in v:
graph[u].append(i)
# graph[i].append(u) #Ungerichtete Grafik
time = 0
arrive_time = [-1] * (N + 1) #Ankunftszeit
finish_time = [-1] * (N + 1) #Suche Endzeit
#Tiefenprioritätssuche
def dfs(v):
global time
time += 1
stack = [v]
arrive_time[v] = time
while stack:
v = stack[-1]
if graph[v]:
w = graph[v].popleft()
if arrive_time[w] < 0:
time += 1
arrive_time[w] = time
stack.append(w)
else:
time += 1
finish_time[v] = time
stack.pop()
return [arrive_time, finish_time]
#Isolierte Apex-Maßnahmen
for i in range(N):
if arrive_time[i + 1] < 0:
ans = dfs(i + 1)
#Spitzenzahl, Ankunftszeit, Endzeit
for j in range(N):
temp = [j + 1, ans[0][j + 1], ans[1][j + 1]]
print(* temp)
Kombinieren Sie einfach die beiden oben genannten. Mit anderen Worten, wenn ein bestimmter Scheitelpunkt erreicht ist oder weniger, läuft die Zeit weiter und sie werden in Ankunftszeit und Endzeit aufgezeichnet.
Ich bin keine Informationsabteilung, deshalb lerne ich anhand von Artikeln und Büchern im Internet. Insbesondere für diese Suche nach Tiefenprioritäten war es für mich als Anfänger sehr schwierig, sie umzusetzen, obwohl die Idee einfach war. (Der Code in diesem Artikel ist möglicherweise auch falsch.) Geben Sie uns daher in den Kommentaren oder auf Twitter einige Ratschläge. Wenn Sie Ratschläge zur Beschleunigung haben, zögern Sie bitte nicht, uns zu kontaktieren.
Recommended Posts