Juste une question rapide et stupide, à propos de BFS traversal sur les graphesnoeud marquage visité sur BFS quand dequeuing
je trouve sur de nombreux sites le pseudo-code pour un BFS est à peu près quelque chose comme ceci:
BFS (Graph, root):
create empty set S
create empty queue Q
add root to S //mark as visited here
Q.enqueue(root)
while Q is not empty:
current = Q.dequeue()
if current is the goal:
return current
for each node n that is adjacent to current:
if n is not in S:
add n to S //mark as visited here
Q.enqueue(n)
Je viens de trouver un peu plus simple de marquer un nœud donné comme visité après l'avoir défini plutôt que d'en avoir un, parce que dans l'approche ultérieure, nous aurons besoin d'écrire une étape supplémentaire. Je sais que ce n'est pas une grande chose, mais je suppose qu'il est plus logique de marquer un nœud comme visité à un endroit au lieu de deux. est plus concis, plus facile à retenir et même à apprendre.
La version modifiée sera comme ceci:
BFS (Graph, root):
create empty set S
create empty queue Q
Q.enqueue(root)
while Q is not empty:
current = Q.dequeue()
add current to s //just add this and remove the other 2 lines
if current is the goal:
return current
for each node n that is adjacent to current:
if n is not in S:
Q.enqueue(n)
Je veux juste savoir si ce changement est correct, pour autant que je sais que cela ne devrait pas changer le comportement du traversal du tout, fait il?