图中有多少个节点是可达的？

Question

我想打印从特定节点可达的节点数。我阅读了图形并存储在邻接列表中并执行了 bfs.i 尝试了以下 code.it 与某些 graph.can 一起工作，你找出了这有什么问题吗？

 #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

returns 2 但实际答案是 3

Answer 1

您正在执行两次 r++。您只能在推送节点或仅弹出节点时执行此操作。否则对于源节点，会计数两次。同时将 r 初始化为 0。为了安全起见，还要手动初始化访问过的数组。

你还拿了 vector<list<int> >::iterator it1=a.begin()+x; 而 a 是空的。 vector<list<int> > a(V); 只是初始化列表的向量，但没有将值放入其中。因此，您尝试遍历的列表是空的。你得到 2 因为你做了两次 r++ 。一个在插入源时，另一个在删除源时给出 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;
    }

图中有多少个节点是可达的？

how many nodes in graph are reachable?

c++

graph

breadth-first-search