Написание глубины сначала поиск в c

Question

Я пытаюсь написать глубину сначала поиск в C. В поиске вместо того, чтобы поддерживать набор всех достижимых узлов, которые мне приходится отметить иссеченное поле в вершине как 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 дважды. Анкет Почему ты делаешь это дважды ???

Более того, первое дополнение выполняется даже без проверки, если сосед уже посетил. Почему? Если вы сделаете это таким образом (т.е. добавьте без проверки, если уже посещается) на циклическом графике, алгоритм перейдет в бесконечный цикл. Он навсегда зацикливается на одном и том же цикле, никогда не достигая других частей графика.

Пс if(currentVertex->isVisited == 0) Проверьте, прежде чем это, вероятно, предотвратит, как бесконечная петля происходит, но все же вышеупомянутое повторное дополнение не имеет для меня смысла.

PPS О, я думаю, что начинаю получать это. Он добавляется дважды намеренно: первое, (безусловное) дополнение, для возврата, второе дополнение (с проверкой) для прогресса прямого DFS. Хм ... может даже сработать, хотя я бы не сделал это так. Вы уверены, что ваш ввод правильный? Подключен ли график, то есть вершина действительно достижимой?