Question

Como implementar o algoritmo de busca exaustiva em grafos conhecido como depth first search - DFS (Busca em profundidade)?

Answer 1

Você pode encontrar duas implementações abaixo: uma usando uma pilha e a outra usando recursão:

import numpy as np

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

def DFSrec(theGraph,explored,source):
    explored[source]=True
    print "theNode: ",source
    for i in theGraph[source]:
        if(not explored[i]):    
            DFSrec(theGraph,explored,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 "DFS: "
    print DFS(theGraph,0)

    explored=np.empty(n,bool)
    for i in range(0,n):
        explored[i]=False


    print "DFSrec: "
    print DFSrec(theGraph,explored,0)