0

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]))
11
  • No entiendo bien qué pretendes. ¿Podrías completar la pregunta con un ejemplo que incluya qué contiene la estructura de datos graph de tu ejemplo y cómo querrías que fuese el diccionario de salida de la función con esos -1 extra?
    – abulafia
    el 6 sep. 2019 a las 8:59
  • Si claro, ya lo logré pero ahora se me presentó otro problema. Ya completo la pregunta
    – Andres
    el 6 sep. 2019 a las 17:50
  • Listo, ya edité la pregunta
    – Andres
    el 6 sep. 2019 a las 17:58
  • Haz nodes=graph.keys() y después for 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.
    – abulafia
    el 6 sep. 2019 a las 18:01
  • Sí, sé que no me estoy dando a entender muy bien jaja. Mi intención es obtener la matriz de distancia a partir de una matriz de adyacencia, como la matriz que pienso trabajar es muy grande 700 x 700 estoy haciendo esto como prueba. Pasar una matriz de adyacencia 10x10 a una lista de adyacencia (y a un diccionario) y aplicar el algoritmo BFS pero tengo problemas cuando me arroja el resultado. Por ejemplo, con tu respuesta me acaba de arrojar el mismo error.
    – Andres
    el 6 sep. 2019 a las 19:09

1 respuesta 1

0

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]))

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.