Python Depth First Search with Dict

Question

I keep seeing pseudocode for Depth First Search that is completely confusing to me in how it relates to my specific problem. I'm trying to determine whether or not a 'directed graph' is strongly connected.

If I have a dict with 2 strings (the first represents the source, the second represents the destination) and an optional number that represents edge weight:

{'Austin': {'Houston': 300}, 'SanFrancisco':  {'Albany': 1000}, 'NewYorkCity': { 'SanDiego': True }}

How can I implement some of the elements of the DFS? I know I can start at a vertex 'Austin' and that 'Houston' is another vertex. But I don't see how any of this works in Python code

Like I have this pseudocode:

function graph_DFS(start):
    # Input: start vertex
    S = new Stack()
    # Mark start as visited
    S.push(start)
    while S is not empty:
        node = S.pop()
        # Do something? (e.g. print)
        for neighbor in node’s adjacent nodes:
            if neighbor not visited:
                # Mark neighbor as visited
                S.push(neighbor)

I can see that I could pass 'Austin' as my start. But how in the world do I set 'Austin' to visited, and how do I see what nodes are adjacent to 'Austin'?

Plus how can I even use this algorithm to return true or false if the graph is strongly connected?

I am just having a really hard time seeing this transfer from pseudocode to code. Appreciate any help.

Your data structure is unsuitable to implement a general graph because it does not allow to have more than one edge from a vertex. The dict values should be lists of destinations. — DYZ

Stuti Rastogi Stuti Rastogi · Accepted Answer · 2017-05-09T05:58:06

I can see that I could pass 'Austin' as my start. But how in the world do I set 'Austin' to visited, and how do I see what nodes are adjacent to 'Austin'?

You can see in the code that you pop out 'Austin', so we will not be looking back at it. In your data structure, you allow only one edge from a vertex, so you will never have more than one neighbor.

Plus how can I even use this algorithm to return true or false if the graph is strongly connected?

This is just a utility DFS function, the algorithm to find whether a graph is strongly connected or not, required running DFS twice. Basically, the hint is you want to know whether you get a tree or a forest on running DFS.

In my opinion, you should update your data structure such that the value of every key is a list (vertices to which it has an edge). You can store weights as well in the list in case you need them later.

Python Depth First Search with Dict

1 Answers