depth first search algoexpert code example

Example 1: 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) #

Example 2: 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)