Question

Python3 question.

Suppose I have a undirect and unweighted graph with vertex list type, here is the code of the graph.

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

I want to use this to create a BFS method. How can I use queue only to finish the work?

Answer 1

CODE

def BFS(graph, start):

visited = {}

for v in graph:

visited[v] = False

queue = []

queue.append(start)

visited[start] = True

while queue:

start = queue.pop(0)

print(start, end=' ')

for node in graph[start]:

if visited[node] == False:

queue.append(node)

visited[node] = True

graph = { "a" : ["c"],

"b" : ["c", "e"],

"c" : ["a", "b", "d", "e"],

"d" : ["c"],

"e" : ["c", "b"],

"f" : []

}

start = 'a'

BFS(graph, start)

​​​​​​​