запись глубины первый поиск в c

Question

Я пытаюсь написать глубину первого поиска в C. В поиске вместо того, чтобы поддерживать набор всех достижимых узлов, я вместо этого должен пометить поле isVisited в Вершине как 1 для посещения. Вот мои структуры данных и моя попытка 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; 

Вот моя попытка реализации 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; 
} 

Проблема с поиском он никогда не возвращает, что узел доступен, даже если она есть. Кто-нибудь знает, как я могу это исправить?

Answer 1

В этом фрагменте кода

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

вы по какой-то причине добавляете соседние вершины currentVertex->neighbors[i] к DFS стек дважды. Почему вы делаете это дважды?

Кроме того, первое дополнение выполняется, даже не проверяя, был ли сосед уже посещен. Зачем? Если вы сделаете это таким образом (т. Е. Добавьте без проверки, если вы уже зашли) в циклическом графе, алгоритм перейдет в бесконечный цикл. Он будет вращаться вокруг одного цикла навсегда, никогда не дойдя до других частей графика.

P.S. Проверка if(currentVertex->isVisited == 0) до этого, вероятно, предотвратит бесконечный цикл, но все же повторное добавление не имеет для меня никакого смысла.

P.P.S. О, я думаю, что я начинаю это делать. Он добавляется дважды намеренно: первое (безусловное) добавление, для возврата, второе дополнение (с проверкой) для продвижения вперед по DFS. Хм ... Могу даже работать, хотя я бы этого не делал. Вы уверены, что ваш ввод верен? Связан ли граф, т. Е. Действительно ли вершина достижима?