BFS分割错误

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

}

这是我的代码来实现广度优先搜索特定的输入文件。输入文件如下：BFS分割错误

我知道我得到了分段错误，同时通过对最后一个顶点邻接表循环，但我不能为我的生活，找出如何解决这个。有什么帮助吗？

编辑：另外，我给起始节点索引为1

来源

2015-04-01 Mysterious

欢迎off-by-one俱乐部。数组是零索引的。在Graph中，您将创建一个大小为V的列表，然后通过Graph::addEdge继续访问V大小的阵列adj的第V个元素。为了解决这个问题，你有两个选择 - 从0到V-1或者adj到V+1的大小。做后者：

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

来源

2015-04-01 06:24:17 Pradhan

BFS分割错误

回答

相关问题