import collections
|
|
from pygraph.graphdemo import Graph
|
|
|
def bfs(g: Graph, start: int) -> {int:int|None}:
|
"""
|
|
:param g:
|
:param start:
|
:return:
|
"""
|
tree = Graph()
|
queue = collections.deque()
|
VISITED = "visited"
|
not_visited = {VISITED: False}
|
visited = {VISITED: True}
|
g.for_each_vertices(lambda v : g.merge_attribute(v, not_visited))
|
queue.append(start) # append() is the enqueue() operation of a Queue
|
g.merge_attribute(start, visited)
|
while queue:
|
u = queue.popleft() # popleft() is the dequeue() operation of a Queue
|
for v in g.adjacent_of(u):
|
if not g.get_attribute(v)[VISITED]:
|
tree.add_edge(u, v)
|
g.merge_attribute(v, visited)
|
queue.append(v)
|
return tree
|
