隣接行列のBFS

Question

私は、ノードの数を返す無向グラフの隣接行列にBFSを実装しようとしています。私はこれまでこれまで考え出してきましたが、トップ/訪問先のノードをプリントアウトしたときと同じではないと思います。ソートされていないだけでなく、いくつかのノードが複数回出現しています。私はどこかでBFSがトポロジカルな並べ替えであり、私が得た順序はソートされていないと読んだ。

int BFS(std::vector<std::vector<int> > &matrix, int start) 
{ 
    std::vector<bool> visited(matrix.size(), false); 
    std::queue<int> Q; 
    Q.push(start); 
    int count = 0; 

    while(! Q.empty()) 
    { 
     int top = Q.front(); Q.pop(); 
     visited[top] = true; count++; 
     for (int i = 0; i < matrix.size(); ++i) 
     { 
      if(matrix[top][i] != 0 && (! visited[i])) 
      { 
       Q.push(i); 
      } 
     } 
    } 
    return count; 
} 

Answer 1

答えを磨くのに役立ついくつかの質問があります。しかし、あなたが戻った数について詳しく説明してください。ここでは見ているものがあります：

• なぜforループ内のカウントをインクリメントしますか？ノードを複数回カウントしている可能性があります。
• のサイズはすべてのノードを保持するのに十分ではありません。 std::vector<bool> visited(matrix.size(), false);では、matrix.size（）は外側のベクトルのサイズのみを返します。つまり、最大で1行分のデータがにあります。にアクセスできます。
• に使用されるデータ構造には問題があります。ベクトル>またはn * n個の要素を1つのシーケンスに持つ線形化されたベクトルを使用します。単純なベクトルを使用する場合は、にアクセスしてインデックスを検索するときに[i] [j]インデックスを位置にマップする必要があります。。これは大きな問題であり、ノードを正しく追跡することはできません。
• ソート順はBFSから保証されません。あなた自身を説得するための簡単な反例を作ってください。トポロジカルソートは、BFS（またはDFS）を使用して実行できます。

Answer 2

キューをポップした後にvisitedノードをtrueに設定する代わりに、ノードをキューに挿入するときにノードを設定し、いくつかのノードの重複カウントを防ぐためにカウントを追加する必要があります。以下を参照してください：

//..previous lines 

Q.push(start); 
visited[start] = true; 
int count = 1; 

while(!Q.empty()){ 
    int top = Q.front(); Q.pop(); 

    for (int i = 0; i < matrix.size(); ++i){ 
     if(matrix[top][i] != 0 && (! visited[i])){ 
      Q.push(i); 
      visited[i] = true; 
      count++; 
     } 
    } 
}