'''Breadth-first graph traversal, separating distances.
Keep separate queues for the current distance and the next distance,
so the end of each distance is noted.
'''
import queue
from DFS import driver, numToChar
def BFSSweepDist(g):
''' display breadth first searches.
g[1:] is a list of lists of adjacent nodes,
g[0] used for directedness and vertex names.
'''
lim = len(g)
visited = [False]*lim
for i in range(1, lim): # ignore index 0 as in g
if not visited[i]:
bfs(g, visited, i)
def bfs(g, visited, v):
'''Breadth first search from vertex v in graph g.
'''
visited[v] = True
q = queue.Queue()
qNext = queue.Queue()
qNext.put(v)
dist = 0
print('Start from', numToChar(v, g))
while not qNext.empty():
q, qNext = qNext, q
print('>>End of vertices at distance', dist)
dist += 1
while not q.empty(): # current distance being processed
v = q.get()
for w in g[v]:
if not visited[w]:
qNext.put(w)
visited[w] = True
print(numToChar(v, g)+numToChar(w, g))
if __name__ == '__main__':
driver(BFSSweepDist, 'A:BCF B:ACD C:ABDF D:BC E:G F:AC G:E')