0

我正在尝试在 C 中编写深度优先搜索。在搜索中，我不必维护一组所有可访问节点，而是必须将 Vertex 中的 isVisited 字段标记为 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;
}

这个搜索的问题是它永远不会返回一个节点是可达的，即使它是可达的。有人知道我该如何纠正吗？

4

1 回答 1

1

在这段代码中

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

您出于某种原因将相邻顶点添加currentVertex->neighbors[i]到 DFS 堆栈两次。你为什么要两次？？？

此外，第一次添加甚至没有检查邻居是否已经被访问过。为什么？如果你这样做（即添加而不检查是否已经访问过）在循环图中，算法将进入无限循环。它将永远围绕同一个循环循环，永远不会到达图表的其他部分。

PSif(currentVertex->isVisited == 0)之前的检查可能会阻止死循环的发生，但是上面的重复添加对我来说仍然没有意义。

PPS 哦，我想我开始明白了。它被有意添加了两次：第一次（无条件）添加，用于回溯，第二次添加（检查）用于前向 DFS 进度。嗯......甚至可能工作，虽然我不会那样做。你确定你的输入是正确的吗？图是连通的，即顶点真的可以到达吗？

于 2010-06-04T22:15:35.620 回答