How do I find the distance from a source node to every other node using Breadth-First Search algorithm in Python

Question

I have a graph that has nodes. For instance, the numbers represent people that know each other. I am using a dictionary, the key is every node and the values is a list of all the people(numbers) the key knows every value. I want to find the distance from the source node to every other node. In the following code, some of the results are incorrect. What am I doing wrong?

import itertools as itt
import operator as op
from typing import List, Dict, AnyStr, Tuple

def loadGraph(edgeFilename):
    array = []
    lst = []

with open(edgeFilename, "r") as f:
    for row in f:
        array.append(row.strip())
array[0] = array[0][1:]
for j in array:
    tup = (j[0], j[-1])
    lst.append(tup)
    
return lst


def to_dict(graph : List[Tuple[AnyStr,AnyStr]]) -> Dict[AnyStr,List[AnyStr]]:
    myDict = {}
    key = op.itemgetter(0)
    val = op.itemgetter(1)
    graph = [list(sorted(e)) for e in graph]
    keys = set(itt.chain.from_iterable(graph))

    for k in keys:
        for v in graph:
            if k in v:
                for j in v:
                    if k != j:
                        if k not in myDict:
                            myDict.update({k : [j]})
                        else:
                            myDict[k].extend([j])
    return myDict

graph = to_dict(loadGraph('d.csv'))

def bfs(graph, s):
queue = []
visited = []
queue.insert(0, s)
visited.insert(0, s)

array = []
dist = 1
level = 1

while queue != []:
    s = queue.pop()
    for i in graph[s]:
        if i not in visited:
            
            array.append({i : dist})
            queue.insert(0, i)
            visited.insert(0, i)
            
            dist=level
    level+=1
    
return array

Driver Code

print(bfs(graph, '2'))

Input would be from a .csv file and would be a list of lists or a list of tuples of every number that knows each other. This would be an undirected graph. If 2 knows 5, then 5 also knows 2.

Input = [[1,2],[2, 3],[1,5,],[3,4],[4,6],[2,5],[2,7],[3,7],[1,8]]

Then through a function would be transformed to a dictionary of everyone that knows each other.

{1:[2,5,8], 2:[1,3,5], 3:[2,4,7], 4:[3,6], 5:[1,2], 6:[4], 7:[2,3], 8:[1]}

This dictionary is the graph. The output I want will tell how far away every node is from the source node.

Example Source node = 2

Output = [{1:1},{3:1},{4:2},{5:1},{6:3},{7:1},{8:2}]

question from:https://stackoverflow.com/questions/65840618/how-do-i-find-the-distance-from-a-source-node-to-every-other-node-using-breadth

Answer 1

Waitting for answers