Tuesday, May 29, 2018

recursive and iterative BFS, DFS,inorder traversal of graph in python

from collections import defaultdict
import queue

#######DFS  RECURSIVE
class node:
    def __init__(self,value):
        self.data = value
        self.left = None        
        self.right  = None
class DFS:
    def __init__(self):
        self.graph =defaultdict(list)
    def dfs_call(self,visited,val):
        if val is None:
            return        
        visited[val] = True        
        print(val)

        for i in self.graph[val]:
            if i is not None:
                if(visited[i]==False):
                    self.dfs_call(visited,i)


    def dfs_recursive(self,val):
        visited = [False]*(len(self.graph))
        self.dfs_call(visited, val)

###### DFS RECURSIVE

#######DFS ITERATIVE for binary tree
def dfs_iter(root):
    visited = [False]*10    
    stack =[]
    stack.append(root)

    while(stack):
        val = stack.pop()
        print (val.data)
        if((val.right  is not None)):
            stack.append(val.right)
        if((val.left  is not None)):
            stack.append(val.left)

###DFS ITERATIVE FOR GRAPH
def dfs_iter_graph(g,len):
    visited = [False]*len
    stack = []
    stack.append(0)
    visited[0]=True
    while(stack):
        val = stack.pop()
        print(val)

        for i in g.graph[val]:
            if i is not None:
                if(visited[i] == False):
                    stack.append(i)
                    visited[i] = True


##INORDER RECURSIVE AND ITERATIVE###########
def inorder(root):
    if(root):
        inorder(root.left)
        print (root.data)
        inorder(root.right)



def inorder_iter(root):
    current =root
    stack = []

    done = 0
    while(not done):
        if(current is not None):

            stack.append(current)
            current =current.left



        else:
            if(stack):
                current = stack.pop()
                print(current.data)

                current = current.right
            else:
                done =1





######BFS WITH QUEUE

def BFS(root,length):
    L = queue.Queue(maxsize=10)
    visited = [False]*length
    L.put(0)
    visited[0] = True
    while( not L.empty()):
        val = L.get()
        print(val)

        for i in g.graph[val]:
            if i is not None:
                if(visited[i] == False):
                    L.put(i)
                    visited[i] == True











root = node(5)
root.left = node(4)
root.right = node(10)
root.left.left = node(3)
root.right.right = node(15)
# inorder_iter(root)
# dfs_iter(root)






g = DFS()
g.graph[0].append(1)
g.graph[0].append(2)
g.graph[1].append(3)
g.graph[1].append(4)
g.graph[2].append(5)
g.graph[2].append(6)
g.graph[3].append(None)
g.graph[3].append(None)
g.graph[4].append(None)
g.graph[4].append(None)
g.graph[5].append(None)
g.graph[5].append(None)
g.graph[6].append(None)
g.graph[6].append(None)
# g.dfs_recursive(0)len = len(g.graph)
print (len)

# dfs_iter_graph(g,len)BFS(g,len)

No comments:

Post a Comment