scrittura ricerca in profondità in c

Question

Sto cercando di profondità di scrittura prima cercare in C. Nella ricerca invece che mantenendo un insieme di tutti i nodi raggiungibili ho invece devono marcare il campo isVisited in Vertex come 1 per visitato. Ecco il mio le strutture di dati e il mio tentativo 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;

Ecco il mio tentativo di implementazione 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;
}

Il problema di questa ricerca è non restituisce mai che un nodo è raggiungibile anche se lo è. Qualcuno sa come potrei correggere questo?

Answer 1

In questo pezzo di codice

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

per qualche motivo sta aggiungendo il vicino vertice currentVertex->neighbors[i] alla pila DFS due volte . Perché si sta facendo due volte ???

Inoltre, la prima aggiunta è fatto senza controllo, anche se il vicino di casa è già stato visitato. Perché? Se lo si fa in questo modo (cioè aggiungere senza controllare se visitato già) in un grafico ciclico l'algoritmo entrerà in un ciclo senza fine. Sarà anello intorno lo stesso ciclo per sempre, senza mai raggiungere altre parti del grafico.

P.S. Il controllo if(currentVertex->isVisited == 0) prima che probabilmente evitare che il ciclo infinito accada, ma ancora sopra aggiunta ripetuta non ha senso per me.

P.P.S. Oh, penso che sto iniziando a farlo. Si aggiunge due volte intenzionalmente: la prima aggiunta, (incondizionata), per backtracking, la seconda aggiunta (con controllo) per il progresso in avanti DFS. Hmm ... potrebbe anche il lavoro, anche se io non lo farei in questo modo. Sei sicuro che il tuo contributo è corretta? È il grafico collegato, cioè è il vertice davvero raggiungibile?