Tengo el siguiente código para la primera búsqueda en profundidad:
def dfs(graph, vertex):
visited = set()
stack = [vertex]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex])
return visited
def main():
test_graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(dfs(test_graph, 'A'))
if __name__ == '__main__':
main()
En cada ejecución obtengo un resultado diferente.
¿Hay algún cambio que pueda hacer para que la salida siempre comience con el valor de vertex
(en este caso, A )?
en Python, a set
no está ordenado. puede usar collections.OrderedDict
para mantener las claves en orden de inserción, mientras que también tiene not in
trabajo en O (1) como en un conjunto:
from collections import OrderedDict
def dfs(graph, vertex):
visited = OrderedDict()
stack = [vertex]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited[vertex] = True
stack.extend(graph[vertex])
return list(visited.keys())
def main():
test_graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(dfs(test_graph, 'A'))
if __name__ == '__main__':
main()
Este artículo se recopila de Internet, indique la fuente cuando se vuelva a imprimir.
En caso de infracción, por favor [email protected] Eliminar
Déjame decir algunas palabras