c - 迭代DFS算法与递归不匹配

Question

我试图通过使用堆栈实现迭代 DFS 算法来查明图中的两个节点是否已连接。然而，为了测试我的解决方案的准确性，我针对用作基线的递归算法运行它。我的算法与递归解决方案的匹配度约为 75%，但我无法确定为什么它没有得到与应有的结果完全相同的结果。

struct Vertex {
    char label;
    int isVisited; // 0 if not yet visited, 1 if yes

    int numNeighbors;
    struct Vertex** neighbors; //list of neighbors of the vertex
};
typedef struct Vertex Vertex;

struct Graph {
    int numEdges;
    int numVertices;
    Vertex* vertexSet;
};
typedef struct Graph Graph;

struct DLink {
  TYPE value;
  struct DLink * next;
  struct DLink * prev;

};

struct cirListDeque {
  int size;
  struct DLink *last;
};

typedef struct cirListDeque cirListDeque;

下面是我尝试使用 cirListDeque 作为堆栈来实现 DFS 搜索:(尝试查找源和目标之间是否存在路径)

int DFS(Graph* g, Vertex* source, Vertex* destination)
{
    /*Need a stack for a depth-first search*/
    cirListDeque stack;
    TYPE vertexCurrent;

    initCirListDeque(&stack);
    addBackCirListDeque(&stack, source);

    while (!isEmptyCirListDeque(&stack))
    {
        //Pop top of the stack
        vertexCurrent = backCirListDeque(&stack);
        removeBackCirListDeque(&stack);


        if (vertexCurrent->label == destination->label)
            return 1;

        for (int i = 0; i < vertexCurrent->numNeighbors; i++)
        {
            if (vertexCurrent->neighbors[i]->label == destination->label)
                return 1;

            if (vertexCurrent->neighbors[i]->isVisited == 0)
            {
                addBackCirListDeque(&stack, vertexCurrent->neighbors[i]);
                vertexCurrent->neighbors[i]->isVisited = 1;
            }
        }
    }

    return 0;
}

我知道它一定有问题，因为我针对这个递归 DFS 算法对其进行了测试，但它并不完全匹配。我知道问题出在我的解决方案中，因为它们正在处理同一个图表。

int DFSRecursiveHelper(Graph* g, Vertex* currVert, Vertex* destination)
{
    int i;

    currVert->isVisited = 1;
    if(currVert == destination)
        return 1;
    for(i = 0; i < currVert->numNeighbors; ++i)
        if(!currVert->neighbors[i]->isVisited)
            if(DFSRecursiveHelper(g, currVert->neighbors[i], destination))
                return 1;
    return 0;
}
int DFSRecursive(Graph* g, Vertex* source, Vertex* destination)
{
    clearVisited(g);
    return DFSRecursiveHelper(g, source, destination);
}

有人能指出我的错误吗？我还尝试过在 for 循环中不检查邻居的标签是否与目的地的标签匹配，结果准确性下降了。

Answer 1

您能更具体地说明什么不起作用吗？

我发现访问顺序有 2 个变化:

1. 递归算法按顺序 1...n 访问邻居，而迭代算法将它们插入堆栈并按相反的顺序 n..1 弹出它们。

2. 递归算法在推送节点时将其标记为已访问。递归变体将其标记为稍后访问。对应弹出的时间。

此外，递归算法在迭代比较标签时检查节点相等性。

vertexCurrent->label == destination->label

对比

currVert == destination