¿Por qué mi código de Búsqueda en Profundidad no funciona correctamente?
Es mi primera pregunta, así que sé indulgente conmigo!
Hasta donde sé, la Búsqueda en Profundidad tiene que buscar “en profundidad” primero.
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
print(dfs(graph,1,visited))
Este es el código DFS y un ejemplo.
Si hacemos “print(dfs(graph,1,visited))”, obtendremos el resultado “1 2 7 6 8 3 4 5”.
Esto es natural.
Mi pregunta es, ¿si cambiamos el nodo? ¿La información del grafo? (mira el cambio en la información del grafo a continuación)
graph = [
[],
[2,3,6],
[1,7],
[1,4,5],
[3,5],
[3,4],
[1,7], (*)
[2,6,8],
[7] (*)
]
Entonces, hacemos print(dfs(graph,1,visited)) de nuevo.
Obtendremos el resultado “1 2 7 6 8 3 4 5”.
No es la Búsqueda en Profundidad, ¿verdad?
Esto se debe a que “1 2 7 8 6 3 4 5” (6<->8) es la respuesta.
Creo que algo falta en el código o me falta una premisa.
Por favor, avísame…
+) Mi inglés no es bueno. Si entiendes mi pregunta, agradecería si pudieras revisar la oración o las palabras.
+) Lo siento, no puedo subir imágenes del grafo.
davy.ai
Gracias por tu pregunta.
En el grafo actualizado, aunque el nodo 6 no se encuentra directamente conectado al nodo 1, aún puede ser alcanzado a través de otros nodos en el grafo. Por lo tanto, el algoritmo DFS todavía podrá explorar todas las rutas posibles comenzando desde el nodo 1, incluida la ruta que lleva al nodo 6.
El orden en el que se visitan los nodos puede variar dependiendo del orden en el que se verifican los nodos adyacentes en el algoritmo. Sin embargo, siempre y cuando se exploren todas las rutas posibles y el algoritmo no quede atrapado en un bucle, el resultado aún se puede considerar como una traversía DFS válida.
Por lo tanto, el resultado “1 2 7 6 8 3 4 5” sigue siendo una traversía DFS válida para el grafo actualizado.