0

我正在尝试通过使用 Prim 算法的随机版本来生成图的生成树。然而，我的程序在生成树生成阶段崩溃了，仔细检查发现了三个不同的错误。

1）在usedEdges.push_back(*i);（在下面的代码中）接收到 SIGTRAP，其中usedEdges类型为std::vector<Edge>。

edges_[edge.From()].push_back(edge);2) 在图形的代码中接收到一个 SIGTRAP ，在非常相似的行edges_：std::vector<std::list<Edge> >

3）当我尝试将边缘的信息打印到终端时，有几次我收到了 SEGFAULT，尽管我无法多次重现它。

如果我理解正确，我收到 SIGTRAP 的事实意味着 Windows 由于内存损坏而触发了某种错误？如果是这样，我的记忆在哪里被破坏了？

生成生成树的代码如下。该maze_成员是一个图，它在内部将节点和边存储在向量和邻接列表中。

typedef std::set<int>                   NodeSet;
typedef std::list<Edge>                 EdgeList;
typedef std::vector<EdgeList>           AdjacencyList;

AdjacencyList       adjacencyList;
std::vector<Edge>   usedEdges;
NodeSet             usedNodes;

//generate grid nodes
for (int i = 0; i < height_; i++)
{
    for (int j = 0; j < width_; j++)
    {
        Node node(maze_.GetNextFreeNodeIndex());
        //nodes.push_back(node);
        maze_.AddNode(node);
        adjacencyList.push_back(std::list<Edge>());
    }
}

//generate grid edges
for (int i = 0; i < height_; i++)
{
    for (int j = 0; j < width_; j++)
    {
        int k = i * width_ + j;

        if (i > 0)
        {
            Edge edge(k, k - width_);
            adjacencyList[k].push_back(edge);
        }

        if (i < height_ - 1)
        {
            Edge edge(k, k + width_);
            adjacencyList[k].push_back(edge);
        }

        if (j > 0)
        {
            Edge edge(k, k - 1);
            adjacencyList[k].push_back(edge);
        }

        if (j < width_ - 1)
        {
            Edge edge(k, k + 1);
            adjacencyList[k].push_back(edge);
        }
    }
}

///Randomized Prim's algorithm
//mark first used node, and add all edges leading from this node to the used edge list.
usedNodes.insert(0);
EdgeList edgeList = adjacencyList[0];
for (EdgeList::iterator i = edgeList.begin(); i != edgeList.end(); i++)
{
    usedEdges.push_back(*i);
}

while (!usedEdges.empty())
{
    int id = LC::rand() * usedEdges.size() - 0.5;
    Edge edge = usedEdges[id];
    if (usedNodes.find(edge.To()) == usedNodes.end())
    {
        maze_.AddEdge(edge);
        usedNodes.insert(edge.To());
        edgeList = adjacencyList[edge.To()];
        for (EdgeList::iterator i = edgeList.begin(); i != edgeList.end(); i++)
        {
            usedEdges.push_back(*i);
        }
    }
    else
    {
        usedEdges.erase(usedEdges.begin() + id - 1);
    }
}

到目前为止我已经尝试过：重建项目，尝试在代码中设置实际断点以观察变量，但到目前为止还没有看到任何异常。然后我又不确定我应该寻找什么......

编辑

Edge 类声明是

class Edge
{
public:
    //Edge(const Edge& edge);
    Edge(int from, int to, float cost);
    Edge(int from, int to);
    Edge();
    virtual ~Edge();

    friend std::ostream& operator<<(std::ostream& os, const Edge& edge);

    int     From() const;
    void    SetFrom(int index);

    int     To() const;
    void    SetTo(int index);

    float   Cost() const;
    void    SetCost(float cost);

    bool operator==(const Edge& rhs);

    bool operator!=(const Edge& rhs);


protected:
    int from_;
    int to_;
    float cost_;
};
4

0 回答 0