鄰接列表C++

Question

我試圖創建一個鄰接列表來存儲圖形。創建該列表時，我遇到了一些問題。

class Weighted_graph { 
private: 
    std::vector <std::vector<std::pair<double, int>> > adjacencyList; 
    ... 
Weighted_graph::Weighted_graph(int n) { 
    std::vector <std::vector<std::pair<double, int>> > adjacencyList(n); 
    for (int i = 0; i < n; i++) { 
     std::vector<std::pair<double, int>> row; // Create an empty row 
     adjacencyList.push_back(row); 
    } 
    ... 
} 

這是我如何創建列表。每當我嘗試列表訪問任何我得到這個錯誤：

Debug Assertion Failed! 
Expression: vector subscript out of range 

發生這種情況時，我嘗試做任何事情與lsit，例如，美其名曰：

bool Weighted_graph::insert_edge(int i, int j, double d) { 
if (!adjacencyList[i].empty()) { 

或

bool Weighted_graph::insert_edge(int i, int j, double d) { 
std::cout << adjacencyList[i].front().second 

我在創建列表錯誤嗎？

Answer 1

一個明顯的問題是'adjacencyList，被定義兩次。首先作爲類的私有成員，第二個作爲大小爲「n」的構造函數中的局部變量。因此，當你想從其他成員函數作爲類成員來訪問它時，它指的是第一個定義，而不是在構造函數中初始化的第一個定義。除非你有特殊的理由這樣做，否則我建議只將它定義爲類數據成員一次，並在構造函數中初始化它，以基於作爲方法參數出現的'n'的值動態設置向量的大小。如果是這樣的話：

class Weighted_graph { 
private: 
    std::vector <std::vector<std::pair<double, int>> > adjacencyList; 
    ... 
    Weighted_graph::Weighted_graph(int n) { 
    adjacencyList.resize(n); 
    for (int i = 0; i < n; i++) { 
     std::vector<std::pair<double, int>> row; // Create an empty row 
     adjacencyList.push_back(row); 
    } 
    ... 
} 

希望有幫助！

Answer 2

使用MAP代替向量是更簡單

#include<iostream> 
#include<map> 
#include<list> 
#include<iterator> 
#include<algorithm> 


using namespace std; 

class Graph 
{ 
private: 
map<int, list<int> > edges = {}; 

public: 
// Read the Intialized Graph and Create a Adjacency list out of it 
// There could be cases where in the initialized graph <map> link issues are 
not maintained 
// for example node 2 to 1 link 
// 2->1 
//there needs to be a link then since undirected Graph 
// 1->2 
Graph(map<int,list<int> > edges) 
{ 
    cout << "Graph is initialized"<<endl; 
    //this->edges = edges; 
    for (auto it : edges) 
    { 
     for (auto di = it.second.begin(); di != it.second.end(); di++) 
     { 
      addEdge(it.first, *di); 
     } 
    } 

} 
//Add a vertex to graph map 
//structure is 
// int => int list 
void addVertex(int vertex) 
{ 
    auto search = edges.find(vertex); 
    if (search != edges.end()) { 
     std::cout << "Already present " << search->first <<endl; 
    } 
    else 
    { 
     list<int> A; 
     edges[vertex] = A; 
    } 

} 

//Add Edge from both vertex to each other 
// Make sure the nodes are present 
void addEdge(int vertex1, int vertex2) 
{ 
    addVertex(vertex1); 
    addVertex(vertex2); 
    if (find(edges[vertex1].begin(), edges[vertex1].end(), vertex2) == edges[vertex1].end()) 
    { 
     edges[vertex1].push_back(vertex2); 
    } 
    if (find(edges[vertex2].begin(), edges[vertex2].end(), vertex1) == edges[vertex2].end()) 
    { 
     edges[vertex2].push_back(vertex1); 
    } 

} 

//Display the graph with vertex and edges 
void display() 
{ 
    for (auto it:edges) 
    { 
     cout << it.first << "::"; 
     for (auto di = it.second.begin(); di != it.second.end(); di++) 
     { 
      cout << "=>" << *di; 
     } 
     cout << endl; 
    } 
} 

};

int main() 
{ 
//A initalized Graph (not in form of adjaceny list 
map<int, list<int> > graph{ { 3, {2} }, 
          { 4, {5} }, 
          { 5, {6} }, 
          { 6, {7} }, 
          { 7, {7} }, 
          { 8, {6} } 
          }; 
//Default constrcutor takes care of making the initialzed map to adjaceny list 
Graph g(graph); 
g.addVertex(1); 
g.addVertex(2); 
g.addVertex(3); 
g.addVertex(4); 
g.addVertex(4); 
g.addEdge(1, 2); 
g.addEdge(2, 2); 
g.addEdge(2, 3); 
g.display(); 


return 0; 
}