Answers for "python depth first search"

python depth first search

# left to right, pre-order depth first tree search, iterative. O(n) time/space
def depthFirstSearch(root):
    st = [root]
    while st:
        current = st.pop()
        print(current)
        if current.right is not None: st.append(current.right) 
        if current.left is not None: st.append(current.left)

dfs python

###############
#The Algorithm (In English):

# 1) Pick any node. 
# 2) If it is unvisited, mark it as visited and recur on all its 
#    adjacent nodes. 
# 3) Repeat until all the nodes are visited, or the node to be 
#    searched is found.


# The graph below (declared as a Python dictionary)
# is from the linked website and is used for the sake of
# testing the algorithm. Obviously, you will have your own
# graph to iterate through.
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set() # Set to keep track of visited nodes.


##################
# The Algorithm (In Code)

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
            
# Driver Code to test in python yourself.
# Note that when calling this, you need to
# call the starting node. In this case it is 'A'.
dfs(visited, graph, 'A')

# NOTE: There are a few ways to do DFS, depending on what your
# variables are and/or what you want returned. This specific
# example is the most fleshed-out, yet still understandable,
# explanation I could find.

python breadth first search

# tree level-by-level traversal. O(n) time/space
def breadthFirstSearch(root):
    q = [root]

    while q:
        current = q.pop(0)
        print(current)
        if current.left is not None: q.append(current.left)
        if current.right is not None: q.append(current.right)

depth first search stack

DFS-iterative (G, s):                                   //Where G is graph and s is source vertex
      let S be stack
      S.push( s )            //Inserting s in stack 
      mark s as visited.
      while ( S is not empty):
          //Pop a vertex from stack to visit next
          v  =  S.top( )
         S.pop( )
         //Push all the neighbours of v in stack that are not visited   
        for all neighbours w of v in Graph G:
            if w is not visited :
                     S.push( w )         
                    mark w as visited


    DFS-recursive(G, s):
        mark s as visited
        for all neighbours w of s in Graph G:
            if w is not visited:
                DFS-recursive(G, w)

depth first search

# HAVE USED ADJACENY LIST
class Graph:
    def __init__(self,lst=None):
        self.lst=dict()
        if lst is None:
            pass
        else:
            self.lst=lst
    def find_path(self,start,end):
        self.checklist={}
        for i in self.lst.keys():
            self.checklist[i]=False
        self.checklist[start]=True
        store,extra=(self.explore(start,end))
        if store==False:
            print('No Path Found')
        else:
            print(extra)
    def explore(self,start,end):
        while True:
            q=[]        
            #print(self.checklist,q)
            q.append(start)
            flag=False            
            for i in self.lst[start]:
                if i==end:
                    q.append(i)
                    return True,q
                if self.checklist[i]:
                    pass
                else:
                    flag=True
                    self.checklist[i]=True
                    q.append(i)
                    break   
            if flag:
                store,extra=self.explore(q[-1],end) 
                if store==False:
                    q.pop()
                    if len(q)==0:return False
                    return self.explore(q[-1],end)
                elif store==None:
                    pass
                elif store==True:
                    q.pop()
                    q.extend(extra)
                    return True,q
            else:
                return False,None
    def __str__(self):return str(self.lst)
if __name__=='__main__':
    store={1: [2, 3, 4], 2: [3, 1], 3: [2, 1], 4: [5, 8, 1], 5: [4, 6, 7], 6: [5, 7, 9, 8], 7: [5, 6], 8: [4, 6, 9], 9: [6, 8, 10], 10: [9],11:[12,13]}
    a=Graph(store)
    a.find_path(1,11) # No Path Found 
    a.find_path(1,6)# [1, 4, 5, 6]    
    a.find_path(3,10)   # [3, 2, 1, 4, 5, 6, 9, 10] 
    a.find_path(4,10)# [4, 5, 6, 9, 10]
    print(a) #

python depth first search

# left to right, pre-order depth first tree search, recursive. O(n) time/space
def depthFirstSearchRec(root):
    if root == None: return
    print(root)
    depthFirstSearch(root.left)
    depthFirstSearch(root.right)