Question

Como implementar o algoritmo de busca exaustiva em grafos conhecido como breadth first search - BFS (busca em largura)?

Answer 1

Uma implementação em python:

import numpy as np
from collections import deque


def BFS(theGraph,source):
    n=len(theGraph)
    explored=np.empty(n,bool)
    for i in range(0,n):
        explored[i]=False
    explored[source]=True
    queue = deque([source])
    while len(queue)!=0:
        v=queue.popleft() 
        print "theNode: ", v 
        for i in theGraph[v]:
            if(not explored[i]):
                explored[i]=True
                queue.append(i)
    return explored    


if __name__ == '__main__':

    n=6 #number of nodes

    theGraph=[set() for i in range(n)]

    theGraph[0].add(1)
    theGraph[0].add(2)
    theGraph[1].add(0)
    theGraph[1].add(3)
    theGraph[2].add(0)
    theGraph[2].add(4)
    theGraph[3].add(1)
    theGraph[3].add(5)
    theGraph[4].add(2)
    theGraph[4].add(5)
    theGraph[5].add(3)
    theGraph[5].add(4)
    print theGraph

print BFS(theGraph,0)