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)