Primera búsqueda de profundidad de escritura en c

Question

Estoy tratando de escribir la profundidad de la primera búsqueda en C. en la búsqueda en lugar de mantener un conjunto de todos los nodos accesibles, en cambio, tengo que marcar el campo ISVisited en Vertex como un 1 para visitado. Aquí están mis estructuras de datos y mi intento 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;

Aquí está mi intento de implementación de 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;
}

El problema con esta búsqueda es que nunca devuelve que un nodo sea accesible incluso si lo es. ¿Alguien sabe cómo podría corregir esto?

Answer 1

En este código

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

por alguna razón está agregando el vértice vecino currentVertex->neighbors[i] a la pila DFS dos veces. ¿Por qué lo haces dos veces?

Además, la primera adición se realiza sin siquiera verificar si el vecino ya ha sido visitado. ¿Por qué? Si lo hace de esa manera (es decir, agregar sin verificar si ya se lo visita) en un gráfico cíclico, el algoritmo entrará en un ciclo interminable. Se convertirá en el mismo ciclo para siempre, sin llegar a otras partes del gráfico.

Ps el if(currentVertex->isVisited == 0) Verifique antes que eso probablemente evitará que ocurra el ciclo interminable, pero aún así la adición repetida anterior no tiene sentido para mí.

PPS Oh, creo que estoy empezando a conseguirlo. Se agrega dos veces intencionalmente: la primera adición (incondicional), para el retroceso, la segunda adición (con verificación) para el progreso de DFS hacia adelante. Hmm ... podría funcionar, aunque no lo haría de esa manera. ¿Estás seguro de que tu entrada es correcta? ¿Está conectado el gráfico, es decir, el vértice es realmente accesible?