如何將節點添加到列表向量中？

Question

我想實現一個使用stl的鄰接列表。我試圖用列表的載體：

std::vector<std::list<int> > graph; 

我的代碼將一個對象添加到圖爲：

graph[size].push_back(8); //8 is an example 
size++; 

每次我嘗試添加一個節點我得到一個分段錯誤，我我不知道爲什麼。將節點添加到此數據結構的正確方法是什麼？

Answer 1

如果你想建立一個帶有鄰接表的圖，你也可以使用unordered_map<std::list<int> > graph。

說，現在要添加節點A和B之間的關係，那麼，所有你需要做的是：

graph[a].push_back() 

添加節點將是簡單：

發現如果節點存在，如果不存在，則將其添加到圖中：

iterator = graph.find(); 

if(iterator != graph.end()) 
{ 
    graph.insert(node);  

} 

這會改善查找和插入時間的複雜性。 現在，您的find（）和insert（）都是O（1）操作。

如果你想與vector<list> graph先走，

使用graph.push_back({x,y,..})

Answer 2

你必須使用分配矢量：

std::vector<std::list<int> > graph(n, std::list<int>())

哪裏n是你圖的節點的數量。

http://ideone.com/udJQrm