これは幅優先探索アルゴリズムですか？

Question

私はこのグラフを持っており、幅優先探索アルゴリズムを使って頂点から別の頂点までのパスがあるかどうかを調べたいと思います。

だから、私はパスの有無に応じて、trueまたはfalseを返すのpythonで関数を実装し、それが動作します。さて、それは私が作ったテストのために働いた。私が知りたいのは、これが実際に呼吸優先検索アルゴリズムである場合です。以前はBFSのアルゴリズムは見ていませんでした。ここで、私は繰り返し、それを実装してもBFSは、再帰的に実装されていることを聞いて、私はit.Soに疑問を持っている理由です機能と私のグラフの表現の両方です：

outb = {1: [2, 3], 
    2: [4, 5], 
    3: [5, 11, 12], 
    4: [6, 7], 
    5: [7], 
    6: [9, 10], 
    7: [8], 
    11: [3], 
    12: [15, 14, 13], 
    13: [17], 
    14: [17], 
    15: [12, 5, 8, 16], 
    17: [18]} 

def BFS(v1, v2): 
    parsed = [] 
    toParse = [v1] 
    current = v1 

    while len(toParse) > 0: 

     while current in parsed: 
      current = toParse.pop(0) 

     if current not in outb: 
      return False 

     if v2 in outb[current]: 
      return True 

     toParse += outb[current] 
     parsed.append(current) 

    return False 

そして、私が持っている最後の質問です：BFSはその性質上、頂点から頂点までの最短経路を見つけるか？私はインターネット上でこのことを読んで、私は確信したい。

Answer 1

これは幅優先による検索です。これは、検索フロンティアがキューとして扱われるかなり典型的な構造に従います（リストはキューにとって非効率的な選択です）。そして、標準的な幅優先探索のように、ルートからの距離順にノードを考慮します。

しかし、それも間違っています。 current not in outbの終了条件では、BFS(1, 18)のような検索ではwrongly output Falseになり、while current in parsed: current = toParse.pop(0)ループではtoParseが消滅し、空リストからポップしようとすると例外がスローされます。demonstrated hereはわずかに異なるグラフです。また、outbは、それが表すはずのグラフの画像と一致しません。 6-> 4のようなバックエッジがたくさんあります。

Answer 2

これはBFSアルゴリズムで、パスが存在するかどうかを調べるために書かれていますが、そのパスが何であるかはわかりません。また、グラフを表すために辞書が構造化されている方法も考慮しません。

ここでは、グラフが辞書を表す方法に対応できるBFSの例を示します。パスが見つかるとパスを返し、パスが存在しない場合はFalseを返します。あなたはちょうどそれがtrueを返すようにしたい場合は、パスを発見したとき、return True

def BFS2(graph, v1, v2): 
    ''' 
    graph: a dictionary representing an unweighted graph 
    v1: a key in graph, representing the start node 
    v2: a key and value in graph, representing the end node 
    returns: a shortest path from v1 to v2, False if there is no path. 
    ''' 
    if v1 not in graph: 
     return False 
    path_start = [v1] 
    paths = [path_start] 
    while len(paths): 
     test_path = paths.pop(0) 
     last_node = test_path[-1] 

     for next_node in graph[last_node]: 
      if next_node not in test_path: 
       next_path = test_path + [next_node] 
       if next_node == v2: 
        paths.append(next_path) 
        return next_path 
       elif next_node in graph: 
        paths.append(next_path) 
    return False 

Answer 3

に編集ライン19はありません、これはBFSアルゴリズムではありません。 This image will show you how a BFS algorithm would work