Lors de la recherche de priorité en profondeur avec python, j'ai entendu dire qu'il y avait un problème de performance avec récursif, j'ai donc décidé de l'implémenter avec stack et je l'ai laissé dans l'article sous forme de mémorandum. J'espère que cela vous aidera à apprendre, et si vous avez des conseils, laissez un commentaire!
Cette fois, nous allons considérer le temps nécessaire pour démarrer un certain sommet et atteindre chaque pic, ce qui est un thème typique dans la recherche de priorité de profondeur. (Est-ce la commande plutôt que l'heure?) À ce moment-là, vérifiez l'heure d'arrivée ** commande en cours **, vérifiez la dernière heure de passage ** ordre de retour **, et enregistrez les deux avec ** horodatage ** Nous traiterons les trois cas. La dernière passe est juste après que la recherche de tous les sommets sous ce sommet soit terminée. Je vais omettre l'explication détaillée de dfs, mais je vais aller plus loin du point de départ à l'endroit où je peux aller, et si je ne peux pas continuer, je reviendrai au point de branchement précédent et répéterai la même chose. Ici, supposons que celui avec le numéro de sommet le plus jeune soit recherché de préférence.
Entrez le nombre de sommets sur la première ligne sous forme d'entier, puis entrez le numéro de sommets, le nombre de sommets adjacents et les sommets adjacents sur la ligne N, séparés par des blancs.
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0
Le numéro de sommet, l'heure d'arrivée et l'heure de fin de recherche sont affichés sur la ligne N, séparés par des espaces. (Seul le premier est dans l'ordre d'aller, et seul le second est dans l'ordre du retour.)
1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6
dfs_1.py
#Recherche de priorité de profondeur (en cours)
import sys
input = sys.stdin.readline
from collections import deque
#Créer un graphique(Dans le graphe non orienté#Effacer)
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 est le nombre de sommets et k est le nombre de sommets adjacents
v.sort()
for i in v:
graph[u].append(i)
# graph[i].append(u) #Graphique non orienté
time = 0
arrive_time = [-1] * (N + 1) #Heure d'arrivée
#Recherche de priorité de profondeur
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
#Mesures d'apex isolés
for i in range(N):
if arrive_time[i + 1] < 0:
ans = dfs(i + 1)
#Numéro de pointe, heure d'arrivée
for j in range(N):
temp = [j + 1, ans[j + 1]]
print(* temp)
Tout d'abord, le graphique est représenté par une liste de contiguïté. Ici, il est considéré comme un graphe orienté, mais il peut également être traité comme un graphe non orienté en supprimant un # dans le code. Le temps peut être traité comme une variable globale sur un axe de temps commun quel que soit le sommet appelé, et lorsqu'un nouveau sommet est atteint, il est incrémenté de +1 et enregistré dans la liste de l'heure d'arrivée arrive_time. Certains graphiques orientés ne peuvent pas être atteints à partir du pic de départ, donc si tous les pics n'ont pas été atteints, une recherche de priorité de profondeur sera effectuée. Puisque la pile est le dernier entré, premier sorti, l'élément arrière est retiré et les sommets adjacents sont examinés. Supprimez ces sommets de la liste de contiguïté afin que vous puissiez voir ce que vous avez examiné. Si le contenu est vide, la recherche du sommet est terminée, supprimez-le de la pile.
dfs_2.py
#Recherche de priorité de profondeur (retour)
import sys
input = sys.stdin.readline
from collections import deque
#Créer un graphique(Dans le graphe non orienté#Effacer)
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 est le nombre de sommets et k est le nombre de sommets adjacents
v.sort()
for i in v:
graph[u].append(i)
# graph[i].append(u) #Graphique non orienté
time = 0
arrive = [-1] * (N + 1) #Es-tu arrivé
finish_time = [-1] * (N + 1) #Heure de fin de la recherche
#Recherche de priorité de profondeur
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
#Mesures d'apex isolés
for i in range(N):
if arrive[i + 1] < 0:
ans = dfs(i + 1)
#Numéro de la fosse, heure de fin
for j in range(N):
temp = [j + 1, ans[j + 1]]
print(* temp)
Les variables et les idées utilisées sont presque les mêmes, mais cette fois, nous enregistrerons l'heure à laquelle la recherche s'est terminée dans finish_time, pas l'heure à laquelle elle est arrivée. En d'autres termes, lors de la suppression d'un sommet adjacent d'un certain sommet de la liste de contiguïté, lorsqu'il devient vide, le temps avance et le temps est enregistré.
dfs_3.py
#Recherche de priorité de profondeur (aller, retour)
import sys
input = sys.stdin.readline
from collections import deque
#Créer un graphique(Dans le graphe non orienté#Effacer)
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 est le nombre de sommets et k est le nombre de sommets adjacents
v.sort()
for i in v:
graph[u].append(i)
# graph[i].append(u) #Graphique non orienté
time = 0
arrive_time = [-1] * (N + 1) #Heure d'arrivée
finish_time = [-1] * (N + 1) #Heure de fin de la recherche
#Recherche de priorité de profondeur
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]
#Mesures d'apex isolés
for i in range(N):
if arrive_time[i + 1] < 0:
ans = dfs(i + 1)
#Numéro de pointe, heure d'arrivée, heure de fin
for j in range(N):
temp = [j + 1, ans[0][j + 1], ans[1][j + 1]]
print(* temp)
Combinez simplement les deux ci-dessus. En d'autres termes, lorsqu'un certain sommet est atteint ou moins, le temps avance et ils sont enregistrés dans arrive_time et finish_time.
Je ne suis pas un service d'information, donc j'étudie en me référant à des articles et des livres sur Internet. Surtout pour cette recherche de priorité en profondeur, même si l'idée était simple, c'était très difficile pour moi en tant que débutant de la mettre en œuvre. (Le code de cet article peut également être incorrect), alors donnez-nous quelques conseils dans les commentaires ou sur Twitter! Si vous avez des conseils pour accélérer, n'hésitez pas à nous contacter.
Recommended Posts