Estoy desarrollando el algoritmo BFS para hallar el camino más corto dentro de un grafo dirigido. El grafo lo estoy trabajando en una lista de adyacencia que después lo derivé a un diccionario. El algoritmo se ejecuta bien
def BFS(graph, s): #graph es el diccionario con el grafo depth = {s: 0} frontier = [s] while len(frontier): current_node = frontier.pop(0) for neighbor in graph[current_node]: if neighbor not in depth: depth[neighbor] = depth[current_node] + 1 frontier.append(neighbor) return depth
Y se imprime bien, aunque no en bloque, toca hacerlo uno por uno. Para la impresión de 3 nodos, devuelve lo siguiente
print(BFS(graph, 1)) print(BFS(graph, 2)) print(BFS(graph, 10))
{1: 0, 6: 1, 7: 2, 2: 3, 8: 4, 3: 5, 4: 6, 9: 7, 5: 8, 10: 9} #nodo 1
{2: 0, 8: 1, 3: 2, 4: 3, 9: 4, 5: 5, 10: 6} #nodo 2
{10: 0} #nodo 3
Como mi intención es hacer una matriz de distancia a partir del algoritmo, mi pregunta es ¿Cómo hago para que me muestre un valor, puede ser ficticio (como -1 o infinito) cuando los nodos no tienen conexión alguna entre ellos? todo con el fin de que cada diccionario tenga el mismo tamaño.
Edit:
Logré establecer el -1 cuando no había conexión con dos nodos distintos, de la siguiente manera
for node in graph: if node not in depth: depth[node] = -1 return depth
{1: 0, 6: 1, 7: 2, 2: 3, 8: 4, 3: 5, 4: 6, 9: 7, 5: 8, 10: 9} #nodo 1
{3: 0, 4: 1, 9: 2, 5: 3, 10: 4, 1: -1, 2: -1, 6: -1, 7: -1, 8: -1} # nodo 2
{10: 0, 1: -1, 2: -1, 3: -1, 4: -1, 5: -1, 6: -1, 7: -1, 8: -1, 9: -1} #nodo 3
sin embargo, cuando quiero imprimir todos los nodos dentro del diccionario de una sola vez mediante:
for node in graph.keys(): print(BFS(graph, node))
Aparece en consola lo siguiente: for node in graph.keys(): RuntimeError: dictionary changed size during iteration
e imprime solo la primera fila, es decir la del nodo 1.
¿Saben cómo resolver este problema? para después poder pasar todo el diccionario a una matriz nxn Gracias
edit: Solución, tienen que crear un diccionario vacío, para que no les aparezca el error
graph = defaultdict(dict) edges = set() for i, v in enumerate(adjacency_matrix, 1): for j, u in enumerate(v, 1): if u != 0 and frozenset([i, j]) not in edges: edges.add(frozenset([i, j])) graph[i].update({j: u}) for i in range(1, len(adjacency_matrix)+1): print("{}: {}".format(i, graph[i]))
graph
de tu ejemplo y cómo querrías que fuese el diccionario de salida de la función con esos -1 extra?nodes=graph.keys()
y despuésfor node in nodes:
Eso evitará el problema de iterar por un diccionario que está siendo modificado dentro de las iteraciones. No obstante, debo reconocer que sigo sin entender bien qué se pretende y sospecho que si lo entendiera podría dar con una solución mejor. Quizás tu función no debería modificar el grafo que recibe como parámetro, sino retornar otro como resultado.