如何使用对象填充图形

Question

我有一个定义如下的对象：

class Item
{
long id;
CString type;
long pointingTo;
};
std::list <Item> itemsFiltered;

让我们假设我在名单上有10个。它们使用id和pointingTo值形成一个图。

10000 - 10001  // id - pointingTo
10001 - 10002
10002 - 10003
10003 - 10004
10005 - 10000
10006 - 10007
10007 - 10003
10008 - 10009
10009 - 10005
10005 - 10000

我试着把图表填成这样：

Graph g = ((long)itemsFiltered.size());
for(auto &it : itemsFiltered)
{
g.addEdge(it.id, it.pointingTo);
}

但这会崩溃(分段错误(。可能是因为我的adj数组大小不足。

我该怎么解决这个问题？在这种情况下，填充图形的更好方法是什么。

这是我使用的图的实现。

class Graph
{
long V; // No. of vertices
// Pointer to an array containing adjacency
// lists
std::list<long> *adj;
public:
Graph(long V); // Constructor
// function to add an edge to graph
void addEdge(long v, long w);
// prints BFS traversal from a given source s
void BFS(long s, std::list<long> listOfIDs);
};
Graph::Graph(long V)
{
this->V = V;
adj = new std::list<long>[V];
}
void Graph::addEdge(long v, long w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(long s, std::list<long> listOfIDs)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
std::list<long> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent
// vertices of a vertex
std::list<long>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
listOfIDs.push_back(s);
queue.pop_front();
// Get all adjacent vertices of the dequeued
// vertex s. If a adjacent has not been visited,
// then mark it visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}

Answer 1

使用大id作为数组的标记似乎访问超出了范围。

如果要使用可以由类型表示的任意值，则应使用std::map(或std::unordered_map，如果您的环境中支持它(。

要使用std::map，请更换

std::list<long> *adj;

带有

std::map<long, std::list<long> > adj;

并删除

adj = new std::list<long>[V];

还有

#include <map>

应该围绕其他标头的CCD_ 5添加到您的程序中。

另一点是

bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;

应该用代替

std::map<long, bool> visited;

以避免超出范围的访问。