グラフ内のノード数に到達可能ですか？

Question

特定のノードから到達可能なノードの数を印刷します。私はグラフを読んで隣接リストに格納し、bfs.iは次のコードを試してみました。特定のgraph.itで動作しましたが、何が間違っているかを追跡できましたか？

#include <vector> 
    #include <iostream> 
    #include <list> 
    #include<queue> 
    using namespace std; 
    int BFS(int s) 
    { 
     const int V=100; 
     int r=0; 
     vector<list<int> > a(V);  
     int visited[V]={0}; 
     queue<int> Q; 
     visited[s]=1; 
     Q.push(s); 
     ++r; 
     while(!Q.empty()) 
     { 
      int x=Q.front(); 
      Q.pop(); // pop here. we have x now 
      ++r; 
      vector<list<int> >::iterator it1=a.begin()+x; 
      list<int> it2=*it1; 
      list<int>::iterator iter=it2.begin(); 
      while(iter!=it2.end()) 
      { 
       if(visited[*iter]==0) 
       { 
        visited[*iter]=1; 
        Q.push(*iter); 

       } 
       ++iter; 
      } 

      visited[x]=2; // set visited here. 

     } 
     return r; 
    } 
    void printAsGrid(int V) 
{ 
    // Create a local 2D projection grid 
    int size = V.size(); 
    double *grid = new double[size*size]; 
    memset(grid, 0.0, size*size*sizeof(double)); 

    // Get the edge connection and weight 
    int index; 
    for (index = 0; index < size; index++) { 
    list<Edge>::const_iterator eit; 
    for (eit = V[index].edges.begin(); 
     eit != V[index].edges.end(); eit++) { 
     int to = (*eit).to; 
     double w = (*eit).weight; 
     // record weight in the projection grid 
     grid[(index*size)+to] = w; 
    } 
    } 

    // print header 
    out << " |"; 
    for (index = 0; index < size; index++) 
    out << " " << index; 
    out << endl; 
    out << "---+"; 
    for (index = 0; index < size; index++) 
    out << "-----"; 
    out << endl; 

    // print content 
    out.setf(ios::fixed); 
    out.setf(ios::showpoint); 
    for (index = 0; index < size; index++) { 
    out << " " << index << " |"; 
    for (int j = 0; j < size; ++j) 
     out << setw(5) << setprecision(1) << grid[(index*size)+j]; 
    out << endl; 
    } 
    // delete grid before exit 
    delete [] grid; 
} 

    int main() 
    { 
     int s; 

     int V,total_neighbors, id, weight; 
     //number of vertices 
     cout<<"enter the no.of vertices:"; 
     cin>>V; 

     vector< list<int> > graph(V + 1); 
     for(int i= 0; i<V;i++) { 
      cout<<"Enter no.of neighbours of"<<i<<":"; 
      cin>>total_neighbors; 
      cout<<"Enter the neighbours of"<<i<<":"; 
      for(int j = 0; j <total_neighbors; j++) { 
       cin>>id; 
       graph[i].push_back(id); 
      } 
     } 
     vector<list<int> >::iterator i; 
     int c=0; 
     for (vector<std::list<int> >::iterator i=graph.begin(); i !=graph.end(); ++i){ 


      cout<<"vertices connected to node "<<c <<" are "; 
      //cout<<*i; 

      std::list<int> li = *i; 
      for(std::list<int>::iterator iter = li.begin(); iter!= li.end(); ++iter){ 

       cout<<*iter<<" "; 
      } 
      cout<<endl; 
      c++; 
    } 
      int f; 
      cin>>f; 
      s=BFS(f); 
      cout<<s<<" "; 
      return 0; 
     } 



adjacencyList 0 -> 1 -> 2 
adjacencyList 1 -> 2 -> 4 
adjacencyList 2 -> 4 
adjacencyList 3 -> 5 
adjacencyList 4 
adjacencyList 5 -> 3 

リターン2が、実際の答えはあなたがR ++ 2回行っている3

Answer 1

です。ノードをプッシュしているとき、または単にノードをポップしているときだけ、これを実行できます。それ以外の場合、送信元ノードは2回カウントされます。また、rを0に初期化します。また、訪問先アレイを手作業で安全な側に初期化します。

また、aが空の場合はvector<list<int> >::iterator it1=a.begin()+x;となりました。 vector<list<int> > a(V);はリストのベクトルを初期化しますが、その中に値を入れません。したがって、トラバースしようとしているリストは空です。あなたはr ++を2回作っているので2を得ています。上記のテストケースのためのあなたのは何である

#include <vector> 
#include <iostream> 
#include <list> 
#include<queue> 
using namespace std; 
int BFS(vector<list<int> > graph, int s) 
{ 
    const int V=100; 
    int r=0; 

    int visited[V]={0}; 
    for(int i = 0; i < V; i++) visited[i] = 0; 
    queue<int> Q; 
    visited[s]=1; 
    Q.push(s); 

    while(!Q.empty()) 
    { 

     int x=Q.front(); 
     cout << x << endl; 
     Q.pop(); // pop here. we have x now 
     ++r; 
     vector<list<int> >::iterator it1=graph.begin()+x; 

     list<int> it2=*it1; 

     list<int>::iterator iter=it2.begin(); 
     while(iter!=it2.end()) 
     { 

      if(visited[*iter]==0) 
      { 
       visited[*iter]=1; 
       Q.push(*iter); 


      } 
      ++iter; 
     } 

     visited[x]=2; // set visited here. 

    } 
    return r; 
} 


int main() 
{ 
    int s; 

    int V,total_neighbors, id, weight; 
    //number of vertices 
    cout<<"enter the no.of vertices:"; 
    cin>>V; 

    vector< list<int> > graph(V + 1); 
    for(int i= 0; i<V;i++) { 
     cout<<"Enter no.of neighbours of"<<i<<":"; 
     cin>>total_neighbors; 
     cout<<"Enter the neighbours of"<<i<<":"; 
     for(int j = 0; j <total_neighbors; j++) { 
      cin>>id; 
      graph[i].push_back(id); 
     } 
    } 
    vector<list<int> >::iterator i; 
    int c=0; 
    for (vector<std::list<int> >::iterator i=graph.begin(); i !=graph.end(); ++i){ 


     cout<<"vertices connected to node "<<c <<" are "; 
     //cout<<*i; 

     std::list<int> li = *i; 
     for(std::list<int>::iterator iter = li.begin(); iter!= li.end(); ++iter){ 

      cout<<*iter<<" "; 
     } 
     cout<<endl; 
     c++; 
} 
     int f; 
     cin>>f; 
     s=BFS(graph,f); 
     cout<<s<<" "; 
     return 0; 
    }