Tiefensuche Adjacency

Question

Programm, das überprüft, ob ein gerichteten Graphen stark

verbunden ist

Ich habe einen defaultdict:

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

Und ein Satz all die unterschiedlichen Zeichenketten enthalten:

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

Hier ist mein 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) 

Hinweis: Mein Standarddict kann gerichtete Strings mit optionalen Kantengewichten enthalten.

Wie kann ich nach einem benachbarten Knoten suchen? Um ehrlich zu sein bin ich nicht 100% sicher, was ein Nachbarknoten in meinem Beispiel ist. Die Verschachtelung verwirrt mich. Danke für jede Hilfe!

Answer 1

Ohne zu viel zu verraten, werde ich das erklären.

Sie können wie folgt über die Tasten eines dict iterieren:

for k in mydict: 
    ... 

In Ihrem Beispiel:

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

Da die Schlüssel für die benachbarten Knoten sind, das ist, wie man auf sie arbeiten können .