profondeur d'écriture première recherche en c

Question

Je suis en train de profondeur d'écriture première recherche en C. Dans la recherche au lieu de maintaing un ensemble de tous les nœuds atteignables que j'ai la place pour marquer le champ isVisited dans Vertex en tant que 1 pour visiter. Voici mes struct de données et ma tentative de algo.

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;

Voici ma tentative de mise en œuvre 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;
}

Le problème avec cette recherche est-il ne retourne jamais qu'un nœud est même accessible si elle est. Quelqu'un sait-il comment je pourrais corriger?

Answer 1

Dans ce morceau de code

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

pour une raison quelconque ajoutez le sommet voisin currentVertex->neighbors[i] à la pile DFS deux fois . Pourquoi fais-tu deux fois ???

En outre, la première addition se fait sans même vérifier si le voisin a déjà été visité. Pourquoi? Si vous le faites de cette façon (à savoir ajouter sans vérifier si déjà visité) dans un graphique cyclique l'algorithme passe en un cycle sans fin. Il boucle autour du même cycle pour toujours, sans jamais atteindre d'autres parties du graphique.

P.S. Le contrôle de if(currentVertex->isVisited == 0) avant cela empêchera probablement la boucle sans fin de se produire, mais ce qui précède l'addition répétée fait aucun sens pour moi.

P.P.S. Oh, je crois que je commence à le faire. Il est ajouté deux fois intentionnellement: le premier, addition (sans conditions), pour faire marche arrière, la deuxième addition (avec vérification) pour le progrès vers l'avant DFS. Hum ... peut-être même travail, même si je ne le ferais pas de cette façon. Etes-vous sûr que votre entrée est correcte? Est-ce le graphique relié, à savoir est le sommet vraiment accessible?