Wie schreibe ich Code für Breitensuche in C++

Question

Ich habe versucht, eine Graphensuche für ein Problem von Hackerrank. Schließlich habe ich kommen mit

#include <cstdio> 
#include <list> 
using namespace std; 

void bfs(list<int> adjacencyList[], int start, int countVertices) { 
    // initialize distance[] 
    int distance[countVertices]; 
    for(int i=0;i < countVertices; i++) { 
     distance[i] = -1; 
    } 

    list<int>::iterator itr; 
    int lev = 0; 
    distance[start-1] = lev;   // distance for the start vertex is 0 
             // using start -1 since distance is array which are 0-indexed 

    list<int> VertexQueue; 
    VertexQueue.push_back(start); 

    while(!VertexQueue.empty()) { 
     int neighbour = VertexQueue.front(); 
     itr = adjacencyList[neighbour].begin(); 

     while(itr != adjacencyList[neighbour].end()) { 
      int vertexInd = (*itr) - 1; 
      if(distance[vertexInd] == -1) {   // a distance of -1 implies that the vertex is unexplored 
       distance[vertexInd] = (lev + 1) * 6; 
       VertexQueue.push_back(*itr); 
      } 
      itr++; 
     } 
     VertexQueue.pop_front(); 
     lev++; 
    } 

    // print the result 
    for(int k=0;k< countVertices;k++) { 
     if (k==start-1) continue;  // skip the start node 
     printf("%d ",distance[k]); 
    } 
} 

int main() { 
    int countVertices,countEdges,start,T,v1,v2; 

    scanf("%d", &T); 

    for(int i=0; i<T; i++) { 
     scanf("%d%d", &countVertices,&countEdges); 

     list<int> adjacencyList[countVertices]; 

     // input edges in graph 
     for(int j=0; j<countEdges; j++) { 
      scanf("%d%d",&v1,&v2); 
      adjacencyList[v1].push_back(v2); 
      adjacencyList[v2].push_back(v1);  // since the graph is undirected 
     } 

     scanf("%d",&start); 

     bfs(adjacencyList, start, countVertices); 
     printf("\n"); 
    } 

    return 0; 
} 

Dies ist jedoch, was zu ‚Segmentation Fault‘ und ich kann nicht herausfinden, wo ich falsch werde. Ich bin auch oft auf Segmentierungsfehler gestoßen, habe aber keine Ahnung, wie man es debuggt. Wäre toll wenn mir jemand eine Idee davon geben könnte.

Answer 1

scanf("%d%d", &countVertices,&countEdges); 
list<int> adjacencyList[countVertices]; 

Der obige Code erscheint falsch. Wenn Ihre Indizes mit 1 beginnen, machen Sie entweder adjacencyList der Größe countVertices + 1 oder verringern Sie u und v, bevor Sie sie in die Liste aufnehmen.

Sie können auch einen (nicht geordneten) Map-Mapping-Vertex zu einer Liste verwenden, die nicht segfault ist.

Auch nicht, dass VLA nicht Teil von Standard-C++ sind, also vermeiden Sie sie, auch wenn Ihr Compiler sie als Erweiterung unterstützt.