'''Breadth-first graph traversal basic algorithm.
'''
import queue
from DFS import driver, numToChar
def BFSSweep(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()
q.put(v)
while not q.empty():
v = q.get()
for w in g[v]:
if not visited[w]:
q.put(w)
visited[w] = True
print(numToChar(v, g)+numToChar(w, g)) # or other action for w
if __name__ == '__main__':
driver(BFSSweep, 'A:BCF B:ACD C:ABDF D:BC E:G F:AC G:E')