$\text{'}\text{'}\text{'}$

Breadth First and Depth First Search

The objective is to write a 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 $(\text{'}$white$\text{'},[\text{'}$b$\text{'}])$

b $(\text{'}$white$\text{'},[\text{'}$c$\text{'}])$

c $(\text{'}$white$\text{'},[\text{'}$a$\text{'},\text{'}$d$\text{'}])$

d $(\text{'}$white$\text{'},[\text{'}$c$\text{'}])$

Root node: a

BFS queue: $($node name, distance$)$ pairs

$[(\text{'}$a$\text{'},0),(\text{'}$b$\text{'},1),(\text{'}$c$\text{'},2),(\text{'}$d$\text{'},3)]$

END BFS

DFS

Input graph: nodeName $($color$,[$adj list$])$ dictionary

a $(\text{'}$white$\text{'},[\text{'}$b$\text{'}])$

b $(\text{'}$white$\text{'},[\text{'}$c$\text{'}])$

c $(\text{'}$white$\text{'},[\text{'}$a$\text{'},\text{'}$d$\text{'}])$

d $(\text{'}$white$\text{'},[\text{'}$c$\text{'}])$

Root node a

graph with root a is cyclic

END DFS

$\text{'}\text{'}\text{'}$

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$==[\text{'}\text{'}]$:continue

# dictionary: key: nodeName value: $($color$,$ adjList of names$)$

gr$[$l$[0]]=(\text{'}$white$\text{'},$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$]=(\text{'}$white$\text{'},$gr$[$e$][1])$

$\text{'}\text{'}\text{'}$

return bfs queue with $($node$,$ distance$)$ pairs

$\text{'}\text{'}\text{'}$

def bfs$($gr$,$ q$)$:

visited $=[]$

while q:

node, distance $=$ q$.$pop$(0)$

visited.append$(($node$,$distance$))$

for nxt in gr$[$node$][1]$:

if gr$[$nxt$][0]==$ 'white':

gr$[$nxt$]=(\text{'}$gray$\text{'},$ gr$[$nxt$][1])$

q$.$append$(($nxt$,$ distance$+1))$

gr$[$node$]=(\text{'}$black$\text{'},$ gr$[$node$][1])$

return visited

def dfs$($gr$,$ node, parent$)$:

global cyclic

if gr$[$node$][0]==$ 'gray':

cyclic $=$ true

return

gr$[$node$]=(\text{'}$gray$\text{'},$ gr$[$node$][1])$

for nxt in gr$[$node$][1]$:

if nxt $!=$ parent:

dfs$($gr$,$ nxt$,$ node$)$

gr$[$node$]=(\text{'}$black$\text{'},$ gr$[$node$][1])$

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$]=(\text{'}$black$\text{'},$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$")$

$!!!!$ The above code has been filled in for DFS and BFS but is continually getting the error: Traceback $($most recent call last$)$:

File $"/$home$/$runner$/$local$/$submission$/$dfbf$.$py$",$ line $116,$ in

gr $=$ read$($sys$.$argv$[1])$ # file name

IndexError: list index out of range