BFS Segmentation Fault

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;

}

This is my code to implement a Breadth first search for a specific input file. The input file is as follows:

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

I know I'm getting the segmentation fault while looping through the adjacency list for the last vertex but I can't, for the life of me, figure out how to fix this. Any help?

Edit: Also, the starting node index I gave is 1.

Answer 1

Welcome to the off-by-one club. Arrays are zero-indexed. In Graph, you create a list of size V and then, through Graph::addEdge, go on to access the V-th element of the V-sized array adj. To fix this, you have two choices - number your vertices from 0 to V-1, or increase the size of adj to V+1. To do the latter:

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