```python # encoding: utf-8 graph = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D", "E"], "D": ["B", "C", "E", "F"], "E": ["C", "D"], "F": ["D"] } def bfs(graph, s): queue = [] queue.append(s) seen = set() seen.add(s) parent = {s : None} while (len(queue) > 0): vertex = queue.pop(0) nodes = graph[vertex] for w in nodes: if w not in seen: queue.append(w) seen.add(w) parent[w] = vertex print vertex return parent def dfs(graph, s): stack = [] stack.append(s) seen = set() seen.add(s) parent = {s : None} while (len(stack) > 0): vertex = stack.pop() nodes = graph[vertex] for w in nodes: if w not in seen: stack.append(w) seen.add(w) parent[w] = vertex print vertex return parent parent = bfs(graph, "A") for key in parent: print(key, parent[key]) print "-----------------------" parent = dfs(graph, "A") for key in parent: print(key, parent[key]) ```