A directed graph connects nodes (a/k/a verticies) with edges. You can read more on Wikipedia Links to an external site.. We're going to represent directed graphs using dictionaries mapping a node to the list of nodes that it has edges to. For example, suppose we have the following graph (from Wikipedia): The nodes are the circles number 1 through 4; the edges are the arrows. The arrow from 1 to 2 has source 1 and target 2. We'd represent it as a Python dictionary as follows: g = {1: [2,3], 2: [], 3:[2, 4], 4: [3]} Notice that the node 2 has no outgoing edges. We could omit its key altogether from the graph, writing: g = {1: [2,3], 3:[2, 4], 4: [3]} These two graphs are equivalent. We'd like you to implement depth-first and breadth-first search. That is, you'll write a file search.py with the following two functions in it, dfs and bfs; each should take in a graph in this dictionary representation. Our graphs will always use numbers for the node. (You can define other helper functions; we won't call them.) It should print out the nodes in appropriate search order. Both DFS and BFS are worklist algorithms: you collect things to do and keep doing them until you run out of things. Start with an empty worklist. Pick the smallest node you can find that you haven't yet visited, and add it to the worklist. While the worklist is not empty: Take a node n off the worklist. If you've seen the node before, go back to 3. If not, print out the node and mark it as visited. Look up the edges coming out of n---add the target to the worklist. If there are nodes you haven't visited yet, go back to step 2. The only difference between DFS and BFS is how steps A and D are performed. In DFS, we use a stack discipline: we add and remove nodes at the same end. In BFS, we use a queue discipline: we add and remove nodes at different ends. There are a many possible DFS and BFS traversals of a graph, depending on the order in which we add the nodes from the edges to our worklist. In order to keep things concrete and easy to grade, please add (i.e., push or enqueue) the nodes in the order they appear in the list. (Hint: use a set to manage which nodes have been seen so far. It will technically break the O(n) complexity, but we're not interested in that here---let's just get our code to work, for now.) Here's a sample interaction with the graph above: >>> g = {1: [2,3], 2: [], 3:[2, 4], 4: [3]} >>> dfs(g) 1 3 4 2 >>> bfs(g) 1 2 3 4