profondeur de l'écriture première recherche dans c

Question

J'essaie d'écrire la première recherche de profondeur en C. Dans la recherche au lieu de maintenir un ensemble de tous les nœuds accessibles, je dois marquer le champ isVisited dans Vertex comme un 1 pour visité. Voici mes structures de données et ma tentative d'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 mon 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 noeud est même si elle est accessible. Est-ce que quelqu'un sait comment je pourrais corriger cela?

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 DFS empilez deux fois. Pourquoi fais-tu ça deux fois ???

De plus, 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 (c'est-à-dire si vous ajoutez sans vérifier si vous avez déjà visité) dans un graphique cyclique, l'algorithme passera dans un cycle sans fin. Il bouclera autour du même cycle pour toujours, n'atteignant jamais d'autres parties du graphique.

P.S. Le if(currentVertex->isVisited == 0) vérifier avant cela empêchera probablement la boucle sans fin de se produire, mais encore l'addition répétée ci-dessus n'a aucun sens pour moi.

P.P.S. Oh, je pense que je commence à l'avoir. Il est ajouté deux fois intentionnellement: le premier ajout (inconditionnel), pour le retour arrière, le second ajout (avec vérification) pour la progression DFS avant. Hmm ... Peut-être même travailler, même si je ne le ferais pas de cette façon. Êtes-vous sûr que votre entrée est correcte? Le graphique est-il connecté, c'est-à-dire que le sommet est réellement accessible?