DictでのPython Depth First Search

Question

Depth First Searchの擬似コードは、私の特定の問題にどのように関係しているか完全に混乱しています。私は、有向グラフが強く接続されているかどうかを判断しようとしています。

Iは、2列（最初のソースを表し、第二の宛先を表す）とエッジの重みを表す任意数の辞書がある場合：

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

どのようにの要素のいくつかを実装することができるがDFS？私は頂点「オースティン」から始めることができ、「ヒューストン」は別の頂点であることを知っています。私は私が私のスタートとして「オースティン」を渡すことができていることがわかります

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) 

：しかし、私は、この擬似コードを持っているように、このいずれかがPythonコード

にどのように動作するか表示されません。しかし、どのように私は「オースティン」を訪問するように設定し、どのノードが「オースティン」に隣接しているかをどのように見ていますか？

さらに、このアルゴリズムを使用して、グラフが強く接続されている場合にtrueまたはfalseを返すことができますか？

私は擬似コードからコードへのこの転送を見ているだけで本当に苦労しています。助けをお待ちしています。

Answer 1

私はオースチンを私のスタートとして渡すことができます。しかし、どのように世界では 私は 'オースティン'を訪問するように設定し、どのノードが「オースティン」に隣接するかを確認するにはどうすればいいですか？

「Austin」がポップアウトしていることがわかりますので、私たちはそれを振り返りません。データ構造では、頂点から1つのエッジのみを許可するので、複数のネイバーを持つことはありません。

さらに、グラフが強く接続されている場合、このアルゴリズムを使用してtrueまたはfalseを返すことができますか？

これは単なるユーティリティDFS関数です。これは、グラフが強く接続されているかどうかを調べるアルゴリズムで、DFSを2回実行する必要があります。基本的には、実行中のDFS上でツリーまたはフォレストを取得するかどうかを知りたいというヒントです。

私の意見では、すべてのキーの値がリスト（エッジがある頂点）であるようにデータ構造を更新する必要があります。後で必要になる場合は、リストに加重を保存することもできます。