在C中写入深度第一次搜索

Question

我正在尝试在C中编写深度搜索。在搜索中，而不是维护所有可触及节点的集合，而是必须将顶点中的iSvised字段标记为1次访问。这是我的数据结构和我的算法尝试。

struct Vertex {
    char label;
    int isVisited;

    int numNeighbors;
    struct Vertex** neighbors;
};
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;

这是我对DFS实施的尝试：

int DFS(Graph* g, Vertex* source, Vertex* destination) {
    cirListDeque stack;
    TYPE currentVertex;
    int i;

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

    while(!isEmptyCirListDeque(&stack)) {
        currentVertex = backCirListDeque(&stack);
        removeBackCirListDeque(&stack);

        if(currentVertex->label == destination->label) {
            return 1;
        }
        else {
            if(currentVertex->isVisited == 0) {
                currentVertex->isVisited = 1;
                for(i = 0; i < currentVertex->numNeighbors; i++) {
                    if(currentVertex->neighbors[i]->label == destination->label) {
                        return 1;
                    }
                    else {
                        addBackCirListDeque(&stack, currentVertex->neighbors[i]);
                        if(currentVertex->neighbors[i]->isVisited == 0) {
                            addBackCirListDeque(&stack, currentVertex->neighbors[i]);
                        }
                    }
                }
            }
        }
    }

    return 0;
}

此搜索的问题在于，即使是节点也无法返回。有人知道我如何纠正吗？

Answer 1

在这件代码中

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

由于某种原因，您正在添加相邻的顶点 currentVertex->neighbors[i] 到DFS堆栈 两次. 。你为什么要这两次？？？

此外，第一个添加是在不检查邻居是否已经访问的情况下完成的。为什么？如果您以这种方式这样做（即添加而无需检查是否已经访问），则在周期性图中，算法将进入无尽的周期。它将永远围绕同一周期循环，从不到达图的其他部分。

PS if(currentVertex->isVisited == 0) 在此之前检查可能会防止无尽的循环发生，但是上述重复的添加对我来说没有意义。

PPS哦，我想我开始得到它。有意添加了两次：第一个（无条件）添加，用于回溯，第二次添加（带检查）进行正向DFS进度。嗯...甚至可能工作，尽管我不会那样做。您确定您的输入是否正确？图形连接了吗，即顶点真的可以到达吗？