如何使用C++編寫廣度優先搜索的代碼

Question

我一直在嘗試從Hackerrank開始針對問題進行圖搜索。最後，我已經拿出

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

但是，這是導致'分段錯誤'，我不知道我要去哪裏錯了。另外，我遇​​到過很多次的分段錯誤，但不知道如何調試它。如果有人能給我一個這樣的想法會很棒。

Answer 1

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

上面的代碼出現錯誤。如果您的指數以1開頭，請將adjacencyList的大小設置爲countVertices + 1，或將u和v加入列表中。

您還可以使用（無序）映射頂點映射到不會出現段錯誤的列表。

也不是說VLA不是標準C++的一部分，所以即使你的編譯器支持它們作爲擴展，也要避免它們。