Modifying Depth First Search with dictionaries
<p>There are a lot of really good DFS python implementations out there, such as <a href="http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/" rel="nofollow">this one</a>, but none of them include cost. I'd like to be able to record the total cost of a DFS path, but this implementation represents the graph as a dictionary of sets.</p>

<pre><code>graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}
</code></pre>

<p>I don't think sets could adequately record cost. So I feel that instead representing the graph as a dictionary of dictionaries would be a good way to implement cost. i.e:</p>

<pre><code>graph = {'A' : {'C' : 10,
                'D' : 7}
                etc.....
</code></pre>

<p>My question is, how could this algorithm be modified to use a this new type of graph instead? I'm still very unfamiliar with python syntax, so seeing an example like this really helps.</p>

<p>Alternatively, if there's an even easier way to represent cost, I'm open to suggestions</p>

<p>EDIT: Okay, here's a different way of thinking about it. How can I modify the code above so that it treats the nested dictionaries similarly to sets?</p>

<p>EDIT2: I believe I've solved it myself, now that I understand the keys() function of dictionaries returns a list.</p>

<p>Looks like <a href="https://networkx.github.io" rel="nofollow">NetworkX</a> is what you are looking for. DFS is included in the package and its graph implementation is what you want. Hope it helps. </p>

python dictionary depth-first-search