c++ - BFS 段错误

Question

#include <iostream>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <list>
// #include "BST.h"

using namespace std;

class Graph
{
  int V; // Number of vertices
  list<int> *adj; // Pointer to the array of adjacency list

public:
  Graph(int V); // Constructor
  void addEdge(int v, int w); // function to add an edge to the graph
  void BFS(int s); // Prints the Breadth first Search for the graph from s.
};

//Defining the constructor
Graph::Graph(int V)
{
  this->V = V;
  adj = new list<int>[V];
}


// Function to add Edges to the vertice.
void Graph::addEdge(int v, int w)
{
  adj[v].push_back(w); // Adding w to v's list
}


// Function to print out the Breadth First Search for the given graph starting at s.
void Graph::BFS(int s)
{
  bool *visited = new bool[V];

  cout << "Value of V: " << V << endl;
  for(int i = 0; i < V; i++)
    visited[i] = false;

  // Create a queue for BFS
  list<int> queue;

  //Marking the starting node as visited and adding it to the queue.
  visited[s] = true;
  queue.push_back(s);

  // Iterator to iterate over the adjacent list vertices
  list<int>::iterator i;

  while(!queue.empty())
  {

    // Printing the current vertex and removing it from the queue
    s = queue.front();
    cout << s << " ";
    queue.pop_front();


    // Going through the adjacency the list and adding it to the queue if it has not been visited.
      for (i = adj[s].begin(); i != adj[s].end(); i++)
      {
        if(!visited[*i] )
        {
          visited[*i] = true;
          queue.push_back(*i);
        }
      }
  }
}



int main(int argc, char* argv[])
{
  // If the user didn't provide a filename command line argument,
  // print an error and exit.
  if (argc != 3)
  {
      cout << "Usage: " << argv[0] << " <Filename>  <starting node index>" << endl;
      exit(1);
  }

  string line;
  int size;
  int starting_vertice;
  char colon;
  int vertex;
  ifstream myfile (argv[1]);
  if (myfile.is_open())
  {
    getline(myfile, line);
    istringstream iss(line);
    iss >> size;

    // Initializing a graph of size taken in.
    Graph g(size);

    cout << "Vertex: " << "Connected Vertices" << endl;
    for (int i = 0; i < size; i++)
    {
      getline(myfile, line);
      istringstream iss(line);
      iss >> starting_vertice;
      iss >> colon;

      while (iss >> vertex)
      {
        g.addEdge(starting_vertice, vertex);
      }
      cout << endl;
    }

    myfile.close();

    cout << "Breadth First Search Starting at vertex " << argv[2] << " : " << endl;
    // cout << atoi(argv[2]) << endl;
    g.BFS( atoi(argv[2]) );
  }

  else
    cout << "Unable to open file" << endl;

  return 0;

}

这是我实现广度优先搜索特定输入文件的代码。输入文件如下:

4
1:2 3 4
2:4
3:4
4:

我知道我在遍历最后一个顶点的邻接列表时遇到段错误，但我无法解决这个问题。有帮助吗？

编辑:另外，我给出的起始节点索引是 1。

Answer 1

欢迎来到 off-by-one俱乐部。数组是零索引的。在 Graph 中，您创建一个大小为 V 的列表，然后通过 Graph::addEdge，继续访问 V-V 大小的数组 adj 的第一个元素。要解决此问题，您有两种选择 - 将顶点编号从 0 到 V-1，或者将 adj 的大小增加到 V+1。要执行后者:

Graph::Graph(int V)
{
  this->V = V;
  adj = new list<int>[V+1];
                     vvvvvv 
}