CODEWITHSUNDEEP
pythondictionarysearchgraph
Coder117
Coder117

Reputation: 851

Depth First Search Adjacency

Program that checks if a directed graph is strongly connected

I have a defaultdict:

defaultdict(<class 'dict'>, {'SanFrancisco': {'Houston': '1000'},
 'LA': {'Ames': '300', 'SanFrancisco': True, 'Detroit': '200'}, 
'NYC': {'LA': '3000'}, 'Austin': {'Houston': '500'}}) 
# myDefaultDict = collections.defaultdict(dict)

And a set containing all the distinct Strings:

{'Austin', 'LA', 'NYC', 'Ames', 'Detroit', 'Houston', 'SanFrancisco'}
# myNewSet

Now here is my code:

for i in myNewSet:
    break
    graph_DFT(i)

def graph_DFT(start):
    functionSet = set()
    myStack = []
    myStack.append(start)
    if not myStack:
        node = myStack.pop()
        # for neighbor in node's adjacent node
            #  if neighbor not visited - i.e. not in functionSet
                  # functionSet.add(neighbor)
                  # myStack.append(neighbor)

Note: My defaultdict can contain directed strings with optional edge weights.

So how can I check for an adjacent node? To be honest I'm not 100% sure what an adjacent node is in my example. The nesting confuses me. Thanks for any help!

Upvotes: 0

Views: 132

Answers (1)

Arya McCarthy
Arya McCarthy

Reputation: 8829

Without giving away too much, I'll explain this.

You can iterate through the keys of a dict like this:

for k in mydict:
    ...

In your example:

for neighbor in G[node]: # Assumes your defaultdict is `G`.
    ...

Since the keys are the adjacent nodes, this is how you can operate on them.

Upvotes: 1

Related Questions