Schreiben der Tiefe erste Suche in C.

Question

Ich versuche, die erste Suche in C in C. in der Suche zu schreiben, anstatt einen Satz aller erreichbaren Knoten zu verwalten, die ich stattdessen das issidierte Feld in Scheitelpunkt als 1 für besuchte markieren muss. Hier sind meine Datenstrukturen und mein Algo -Versuch.

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;

Hier ist mein Versuch bei einer DFS -Implementierung:

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;
}

Das Problem bei dieser Suche ist, dass es nie zurückgibt, dass ein Knoten auch dann erreichbar ist. Weiß jemand, wie ich das korrigieren könnte?

Answer 1

In diesem Code

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

Sie addieren aus irgendeinem Grund den benachbarten Scheitelpunkt currentVertex->neighbors[i] zum DFS -Stack zweimal. Warum machst du es zweimal ???

Darüber hinaus erfolgt die erste Ergänzung, ohne zu überprüfen, ob der Nachbar bereits besucht wurde. Wieso den? Wenn Sie es so tun (dh hinzufügen, ohne bereits zu überprüfen, ob es bereits besucht wird) in einem zyklischen Diagramm wird der Algorithmus in einen endlosen Zyklus übergeht. Es wird für immer im selben Zyklus umgehen und nie andere Teile des Diagramms erreichen.

Ps die if(currentVertex->isVisited == 0) Überprüfen Sie, ob dies wahrscheinlich verhindern wird, dass die endlose Schleife stattfindet, aber die oben genannte wiederholte Ergänzung macht für mich keinen Sinn.

PPS Oh, ich glaube, ich fange an, es zu bekommen. Es wird zweimal absichtlich hinzugefügt: die erste (bedingungslose) Addition zum Rückverfolgen, die zweite Zugabe (mit Überprüfung) für den Fortschritt des Vorwärtsdfs. Hmm ... könnte sogar funktionieren, obwohl ich es nicht so machen würde. Sind Sie sicher, dass Ihre Eingabe korrekt ist? Ist die Grafik verbunden, dh ist der Scheitelpunkt wirklich erreichbar?