The return value for the tree edges list - a list of the edges in the DFS search tree - is not correct. I am not quite sure at what point in the function I implemented the code incorrectly. I am thinking in the
for loop, but I am not sure. Here is the code.
# the input graph is:
input_graph = {1:[3,4,8,9,11], 2:[3,8,12], 3:[1,2,5,11], 4:[1,6,9,10], 5:[3,12], 6:[4,10], 7:[8,12], 8:[1,2,7,10], 9:[1,4,11], 10:[4,6,8], 11:[1,3,9], 12:[2,5,7]}
def DFS(graph, root):
parent_dictionary = {}
parent_dictionary[root] = None
visited = [root]
tree_edges = []
w = root
i = 0
n = len(graph.keys())
while i < (n-1):
for vertex in graph[w]:
if vertex not in visited:
visited.append(vertex)
tree_edges.append((w,vertex))
parent_dictionary[vertex] = w
w = vertex
i += 1
w = parent_dictionary[w]
return tree_edges
print(DFS(input_graph, 1)) # Print value is: [(1, 3), (3, 4), (4, 8), (8, 9), (9, 11), (8, 2), (2, 7), (7, 10), (7, 12), (4, 6), (3, 5)]
# The print value should be [(1,3), (3,2), (2,8), (8,7), (8,10), (7,12), (12,5), (10,4), (4,6), (4,9), (9,11)]
# From the correct return value, I can then build the DFS tree, rooted at 1, which is:
DFS_tree = {1:[3],3:[2],2:[8],8:[7,10],7:[12],12:[5],5:[],10:[4],4:[6,9],6:[],9:[11],11:[]}