#369 Complete the Breadth First and Depth

Complete the Breadth First and Depth - Computer Science

ChemistryExplain daily providing Q&A content “#369 Complete the Breadth First and Depth" in Computer science, Ba computer science, Berkeley computer science, Computer science associate degree jobs

Get the Free Online Chemistry Q&A Questions And Answers with explain. To crack any examinations and Interview tests these Chemistry Questions And Answers are very useful. Here we have uploaded the Free Online Chemistry Questions. Here we are also given the all chemistry topic.

 ChemistryExplain team has covered all Topics related to inorganic, organic, physical chemistry, and others So, Prepare these Chemistry Questions and Answers with Explanation Pdf.

For More Chegg Questions

• Inorganic Chemistry
• Organic Chemistry
• Physical Chemistry

Free Chegg Question

(Python) Complete the Breadth First and Depth First Search functions
--------------------------------------------------------------------------------------------------------------------------- 

dfbf.py file (Do change your main, particularly to test your code on different types of graph (cyclic, non cyclic, all nodes reachable from the root, not all nodes reachable from the root)

import sys

#global variable, keeping track in dfs whether a cycle was found
cyclic = False 

# Don't change helper functions
#   read, dump, white, dfsInit

def read(fnm):
  """  
  read file fnm containing a graph into a dictionary and return the dictionary
  each line has a nodeName followed by its adjacent nodeNames
  """
  f = open(fnm)
  gr = {} #graph represented by dictionary
  for line in f:
    l =line.strip().split(" ")
    # ignore empty lines
    if l==['']:continue
    # dictionary: key: nodeName  value: (color, adjacency List of names)
    gr[l[0]]= ('white',l[1:]) 
  return gr

def dump(gr):
  print("Input graph: nodeName (color, [adj list]) dictionary ")
  for e in gr:
    print(e, gr[e])

def white(gr) :
  """
   paint all gr nodes white
  """
  for e in gr :
    gr[e] = ('white',gr[e][1])

def dfsInit(gr,root):
   """
   dfs keeps track of cycles in global cyclic
   call dfs with appropriate initial parameters
   """ 
   global cyclic
   cyclic = False
   visited = dfs(gr,root,[])
   return (visited,cyclic)

# Work on bfs, dfs 

def bfs(gr,q):
  """
  q is an array representing a queue of (node,distance) pairs
  initially queue q contains 1 (node,distance) pair: (root,0)
  (see the call to bfs in main)
  breadth first search gr from the root, keep track of distance
  from root
  return the queue of all (node,distance) pairs visited
  """
  return q

      
def dfs(gr,r,visited):
   """  
   depth first search gr from root r for cycles,
   when a cycle is detected, set global cyclic to True
   return array of nodes visited, i.e. append node to visited
   when encountering it for the first time (i.e. when it is white)
   """
   global cyclic
   return visited



if __name__ == "__main__":
  print(sys.argv[0])      # program name
  gr = read(sys.argv[1])  # graph file name
  root = sys.argv[2]      # root node
  print("BFS")
  dump(gr)
  print("Root node:", root)
  # don't need grey for bfs
  gr[root] = ('black',gr[root][1])
  q = bfs(gr,[(root,0)])
  print("BFS queue: (node name, distance) pairs")
  print(q)
  print("END BFS")
  print()
  white(gr);
  print("DFS")
  dump(gr)
  print("Root node", root)
  vis,cyc = dfsInit(gr,root)
  print("DFS from root visited:")
  print(vis)
  if cyc:
    print("graph with root",root,"is cyclic")
  else:
    print("graph with root",root,"is not cyclic")
  print("END DFS")

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

(Input) in1 a

a b c d

b
c d
d e f
e a
f g
g f

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

OUTPUT Example

python3 dfbf.py in1 a

dfbf.py
BFS
Input graph: nodeName (color, [adj list]) dictionary 
a ('white', ['b', 'c', 'd'])
b ('white', [])
c ('white', ['d'])
d ('white', ['e', 'f'])
e ('white', ['a'])
f ('white', ['g'])
g ('white', ['f'])
Root node: a
BFS queue: (node name, distance) pairs
[('a', 0), ('b', 1), ('c', 1), ('d', 1), ('e', 2), ('f', 2), ('g', 3)]
END BFS

DFS
Input graph: nodeName (color, [adj list]) dictionary 
a ('white', ['b', 'c', 'd'])
b ('white', [])
c ('white', ['d'])
d ('white', ['e', 'f'])
e ('white', ['a'])
f ('white', ['g'])
g ('white', ['f'])
Root node a
DFS from root visited:
['a', 'b', 'c', 'd', 'e', 'f', 'g']
graph with root a is cyclic
END DFS

Free Chegg AnswerFor More Chemistry Notes and Helpful Content Subscribe Our YouTube Chanel - Chemistry Explain  

Free Chegg Answer

Code:

import sys

# global variable, keeping track in dfs whether a cycle was found
cyclic = False


# Don't change helper functions
#   read, dump, white, dfsInit

def read(fnm):
    """
    read file fnm containing a graph into a dictionary and return the dictionary
    each line has a nodeName followed by its adjacent nodeNames
    """
    f = open(fnm)
    gr = {}  # graph represented by dictionary
    for line in f:
        l = line.strip().split(" ")
        # ignore empty lines
        if l == ['']: continue
        # dictionary: key: nodeName  value: (color, adjacency List of names)
        gr[l[0]] = ('white', l[1:])
    return gr


def dump(gr):
    print("Input graph: nodeName (color, [adj list]) dictionary ")
    for e in gr:
        print(e, gr[e])


def white(gr):
    """
     paint all gr nodes white
    """
    for e in gr:
        gr[e] = ('white', gr[e][1])


def dfsInit(gr, root):
    """
    dfs keeps track of cycles in global cyclic
    call dfs with appropriate initial parameters
    """
    global cyclic
    cyclic = False
    visited = dfs(gr, root, [])
    return (visited, cyclic)


# Work on bfs, dfs

def bfs(gr, q):
    """
    q is an array representing a queue of (node,distance) pairs
    initially queue q contains 1 (node,distance) pair: (root,0)
    (see the call to bfs in main)
    breadth first search gr from the root, keep track of distance
    from root
    return the queue of all (node,distance) pairs visited
    """
    # Maintain an array to store visited nodes
    seen = [q[0][0]]
    for node in q:
        distance = node[1] + 1

        # Traverse the rapg
        for adjacent in gr[node[0]][1]:
            if adjacent in seen:
                # Continue is node is already visited
                continue
            else:
                q.append((adjacent, distance))
            seen.append(adjacent)       # Mark the 'adjacent' node visited
    # Return the queue
    return q


def dfs(gr, r, visited):
    """
    depth first search gr from root r for cycles,
    when a cycle is detected, set global cyclic to True
    return array of nodes visited, i.e. append node to visited
    when encountering it for the first time (i.e. when it is white)
    """
    # Maintain a global variable cyclic
    global cyclic
    # If r is not in visited, mark r visited
    if r not in visited:
        visited.append(r)
    else:
        cyclic = True
        return

    # Recursively perform dfs for every noce
    for node in gr[r][1]:
        dfs(gr, node, visited)

    return visited


if __name__ == "__main__":
    print(sys.argv[0])  # program name
    gr = read(sys.argv[1])  # graph file name
    root = sys.argv[2]  # root node
    print("BFS")
    dump(gr)
    print("Root node:", root)
    # don't need grey for bfs
    gr[root] = ('black', gr[root][1])
    q = bfs(gr, [(root, 0)])
    print("BFS queue: (node name, distance) pairs")
    print(q)
    print("END BFS")
    print()
    white(gr);
    print("DFS")
    dump(gr)
    print("Root node", root)
    vis, cyc = dfsInit(gr, root)
    print("DFS from root visited:")
    print(vis)
    if cyc:
        print("graph with root", root, "is cyclic")
    else:
        print("graph with root", root, "is not cyclic")
    print("END DFS")

Code Screenshots:

Output screenshots:

Input file used:

a b c d
b
c d
d e f
e a
f g
g f

This file wasn't provided but I tried to create it from the output. Hope this helps.

-------------------------END---------------------

Hope this helps you. Do comment if you have any doubts.

Please give a thumbs up(upvote) if you liked the answer.

Thank You