BFS.py

BFS.py

def BFS(G,s):
	Q = []
	state = [None for i in range(len(G))]
	pi = [None for i in range(len(G))]
	
	for u in range(len(G)):
		state[u]='N'
		pi[u] = None
		
	state[s] = 'D'
	pi[s] = None
	Q.append(s)
	
	while Q != []:
		u = Q.pop(0)
		print(u)
		
		for v in G[u]:
			print(u,v)
			if(state[v] == 'N'):
				state[v] = 'D'
				pi[v] = u
				Q.append(v)
		state[u] = 'P'
	
	for i in range(len(pi)):
		print("Pai de", i ,"eh",pi[i])
		
def main():
	#G eh a minha lista de adjacencias
	G=((1,4),(0,2,3,4),(1,3),(1,2,4),(0,1,3))

	BFS(G,0)
	
if __name__ == '__main__':
	main()