Wie viele Knoten im Diagramm sind erreichbar?

Question

Ich möchte die Anzahl der Knoten drucken, die von einem bestimmten Knoten aus erreichbar sind. Ich lese Graph und in der Adjazenzliste gespeichert und führte bfs.i hatte den folgenden Code versucht.Es funktioniert mit bestimmten graph.Can Sie verfolgt, was ist los damit?

#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 

kehrt 2, aber tatsächliche Antwort ist 3

Answer 1

Du r ++ zweimal tun. Sie können es nur tun, wenn Sie den Knoten drücken oder wenn Sie nur den Knoten öffnen. Andernfalls wird es für den Quellknoten zweimal gezählt. Initiiere auch r auf 0. Initialisiere das besuchte Array auch manuell, um auf der sicheren Seite zu sein.

Auch Sie haben vector<list<int> >::iterator it1=a.begin()+x; genommen, während a leer ist. vector<list<int> > a(V); initialisiert nur den Vektor der Liste, setzt aber keine Werte hinein. Und damit ist die Liste, die Sie durchqueren wollen, leer. Du bekommst 2, weil du r ++ zweimal machst. Eine, wenn die Quelle eingeführt wird und andere, wenn die Quelle entfernt, die Sie gibt 2.

diesen Code Siehe:

#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; 
    }