CS320 Recit 2

Here is a python skeleton codes exDct.py, which reads a adjacency list representation of a graph, eg from inD. The file containing the adjacency list has one line for each node with format:

nodeName adjacent_nodeNames seperated by spaces.

The skeleton code reads these lines into a dictionary, and prints the resulting graph, the root and its adjacent nodes. Command line call, eg
exDct.py inD a d
reads file inD, makes a the root, and puts the program in debug mode.

Use this skeleton code to create two programs: dfs.py and bfs.py.

dfs.py should traverse the graph, from the root, depth first and should detect all cycles. If, eg, the input file is

a b c
b d
c
d a

and the root is a, then a cycle should be detected when d visits a, eg

found cycle in a

bfs.py should traverse the graph, from the root, breadth first and should print a list of the nodes that are connected to the root, and their distance, in number of edges, from the root. If, again, the input file is

a b c
b d
c
d a

and the root is a, then bfs.py should report

[('a', 0), ('b', 1), ('c', 1), ('d', 2)]