如何在图中标记已访问顶点

Question

我正在为迷宫程序中的寻路实现图形结构。在某些操作中，如：遍历图，释放图（之前是malloc-ed，或使用广度优先搜索，...需要检查是否访问了顶点。

这是vertex和edge结构：

typedef struct graph
{
    // val just use to label the vertex
    int val;

    // since the maze just has 4 directions,
    // I simplify vertex to just point to 4 other vertices
    edge up;
    edge down;
    edge left;
    edge right;
}vertex;

typedef struct Edge
{
    int weight;
    vertex *neighbour;
    bool visited;
}edge;

我想过2个解决方案。第一种是在vertex或edge结构中添加bool visited;并初始化为false，但只能使用1次，因为我不知道如何重新初始化visited。第二种方法是制作一个 link 列表，将访问过的顶点放入该列表中，并在需要时检查该列表中的访问过的顶点。但是当有数百个顶点时，它会花费很多工作。

那么检查顶点是否被访问的好机制是什么？解决这个问题的更好方法是什么？

Answer 1

对于你的第一个解决方案，你可以将 bool visited 添加到边和顶点，并且每当你访问某些东西时，你将它添加到链表中，所以当你完成并且你想要 re-initialize 他们假你在链表上进行一次传递并更新它们的值，然后清除链表。

另一个解决方案是，当您访问一个节点或一条边时，您将它们放在一些平衡的二叉搜索树中（映射、集合...或您自己实现的东西），这些允许您添加一个元素或检查 O(log(n)) 中是否存在元素，其中 n 是元素总数。