Question
''' Breadth First and Depth First Search The objective is to write Python program that traverses graphs in BFS and DFS manner. BFS will determine
'''
Breadth First and Depth First Search
The objective is to write Python program that traverses graphs in BFS
and DFS manner. BFS will determine the shortest path distance (number of
edges) from the root for each node reachable from the root. DFS will find
cycles in the graph of nodes reachable from the root. Study the lecture on
graphs, in particular graph traversals.
Some helper code is provided. Don't change it. Don't change your main,
it is used to check your code's correctness.
It is your job to implement dfs and bfs. In both dfs and bfs, visit
children of a node in left to right order, i.e., if adj is the
adjacency list of a node, visit the children as follows: for nxt in adj
Given an input file in:
a b
b c
c a d
d c
and root a
python dfbf.py in a produces:
dfbf.py
BFS
Input graph: nodeName (color, [adj list]) dictionary
a ('white', ['b'])
b ('white', ['c'])
c ('white', ['a', 'd'])
d ('white', ['c'])
Root node: a
BFS queue: (node name, distance) pairs
[('a', 0), ('b', 1), ('c', 2), ('d', 3)]
END BFS
DFS
Input graph: nodeName (color, [adj list]) dictionary
a ('white', ['b'])
b ('white', ['c'])
c ('white', ['a', 'd'])
d ('white', ['c'])
Root node a
graph with root a is cyclic
END DFS
'''
import sys
cyclic = False #keeping track in dfs whether a cycle was found
def read(fnm):
"""
read file fnm into 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: nodeNamevalue: (color, adjList 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])
'''
return bfs queue with (node, distance) pairs
'''
def bfs(gr,q):
for node in q:
for edge in gr[node[0]][1]:
if gr[edge][0] == 'white':
gr[edge] = ('black', gr[edge][1])
q.append((edge, node[1]+1))
return q
def dfs(gr,r):
global cyclic
if gr[r][0] == 'black':
cyclic = True
return cyclic
gr[r] = ('black', gr[r][1])
for edge in gr[r][1]:
dfs(gr, edge)
return cyclic
if __name__ == "__main__":
print(sys.argv[0])
gr = read(sys.argv[1])# file name
root = sys.argv[2]# root node
db = len(sys.argv)>3# debug?
print("BFS")
dump(gr)
print("Root node:", root)
gr[root] = ('black',gr[root][1])
q = bfs(gr,[(root,0)])
print("BFS queue: (node name, distance) pairs")
print(q)
print("END BFS")
print()
print("DFS")
white(gr)
dump(gr)
print("Root node", root)
dfsInit(gr,root)
if cyclic:
print("graph with root",root,"is cyclic")
else:
print("graph with root",root,"is not cyclic")
print("END DFS")
=====================================================================
This was the code that is given and I tried the code below for bfs and dfs
def bfs(gr,q):
for node in q:
for edge in gr[node[0]][1]:
if gr[edge][0] == 'white':
gr[edge] = ('black', gr[edge][1])
q.append((edge, node[1]+1))
return q
def dfs(gr,r):
global cyclic
if gr[r][0] == 'black':
cyclic = True
return cyclic
However, I got error that says
Traceback (most recent call last):
File "dfbf.py", line 160, in
dfsInit(gr,root)
NameError: name 'dfsInit' is not defined
Also, last two lines for DFS were missing.
It should print graph with root a is cyclic and END DFS when root node a
but mine only print until root node a.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started