デプスファーストサーチインプリメンテーションの出力が正しくない

Question

最近、私はウェブサイト（https://brilliant.org/wiki/depth-first-search-dfs/）でデプスファーストサーチのコードを探していました。しかし、彼らの実装はcompletly correct.Thisではありませんあなたが見ることができるように、彼らは

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

投稿をコードで、それらが適用ロジックが正しいですが、彼らは毎回プログラムの実行を出力を変更する設定操作を使用していました。

これは私の完全なプログラムである

graph = {'A': {'B', 'S'}, 'B': {'A'}, 'C': {'S', 'F', 'D', 'E'}, 
    'D': {'C'}, 'E': {'H', 'C'}, 'F': {'C', 'G'}, 'G': {'S', 'F', 'H'}, 
    'H': {'G', 'E'}, 'S': {'A', 'G', 'C'}} 

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

print(depth_first_search(graph, 'A')) 

以下は、私がプログラムを実行evertime私が手に出力がある

{'H', 'C', 'B', 'A', 'D', 'S', 'F', 'E', 'G'} 
{'D', 'E', 'C', 'H', 'G', 'S', 'A', 'B', 'F'} 
{'G', 'F', 'C', 'H', 'E', 'D', 'B', 'S', 'A'} and so on.... 

設定した理由は、特に我々のようにコードの下の行のために理にかなっています未探索の頂点だけをスタックに格納するようにします。

ように設定差分演算は、私はセットを使用して回避し、リスト

graph = {'A': ['B', 'S'], 'B': ['A'], 'C': ['S', 'F', 'D', 'E'], 
'D': ['C'], 'E': ['H', 'C'], 'F': ['C', 'G'], 'G': ['S', 'F', 'H'], 
    'H': ['G', 'E'], 'S': ['A', 'G', 'C']} 

def depth_first_search(graph, root): 
    visited, stack = [], [root] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.append(vertex) 
      neighbours = graph[vertex] 
      for neighbour in neighbours: 
       # ensures we only add unexplored nodes to the stack 
       if neighbour not in visited: 
        stack.append(neighbour) 
    return visited 

print(depth_first_search(graph, 'A')) 

をどう作るために、コードを少し微調整above.So述べたように、それはコストがかかりますobjective.Butことを達成するが実行

stack.extend(graph[vertex] - visited) 

私は、正しい結果が

でなければなりません

['A', 'S', 'C', 'E', 'H', 'G', 'F', 'D', 'B'] 

間違った結果を取得します10

私は間違っていますか？

Answer 1

あなたが得ている答えは、そのグラフの有効なDFS順序です。ノードの隣人がアルファベット順に横断されなければならないという書かれていない制限があるようです。これを念頭に置いて、2つのことを考えてみましょう。

まず、定義されている順序でノードのネイバーをスタックに追加します。しかし、あなたがpop()をスタックから外したときは、最後のアイテムを最初にスタックから外してください。つまり、ノードを逆順に選択しています。それはあなたが隣人を反復する順序を逆にすることによって解決することは簡単です：

for neighbour in reversed(neighbours): 

第二には、あなたが実際にアルファベット順ににノードの隣人を定義していません。あなたのいずれかの定義での値をアルファベット順、または反復前にそれらをソートする必要があります。

for neighbour in reversed(sorted(neighbours)): 
# or 
for neighbour in sorted(neighbours, reverse=True): 

Answer 2

それはあなたが持っている最初のコードサンプルは、トポロジカルソートを生成するために意図されていないように見えますが、単純にすべて一覧表示しますルートから到達できるノード。おそらくそれが間違っているわけではないことに注意することが重要です、それはちょうどあなたに命令を与えることになっていません。

あなたのコードは基本的にそれがすべきことを言います。あなたが得ている出力はあなたが期待しているものと同じです。限り、DFSが必要なだけです。

vertex = stack.pop()を呼び出すと、最後の（つまり一番右の要素）が返されることを忘れています。stack.append(neighbour)に電話すると、子をスタックにプッシュしています左から順に

"左端"分岐を最初に通過するDFSを必要とする場合、それらをスタックに追加する前に、隣接/子の順序を逆にする必要があります。

EDIT：私は自由にコメントするのに十分な担当者がいませんが、私の答えは基本的にglibdud'sと同じです。あなたが走っている問題は、基本的なDFSの一部ではないあなたの頭に追加の制限を適用しているようです。