глубина записи первый поиск в с - PullRequest
Новая
       20

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

0 голосов
/ 05 июня 2010

Я пытаюсь записать глубину поиска сначала в C. В поиске вместо того, чтобы поддерживать набор всех достижимых узлов, я вместо этого должен отметить поле isVisited в Vertex как 1 для посещенного. Вот мои структуры данных и моя попытка алгоритма. 

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

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

1 Ответ

1 голос
/ 05 июня 2010

В этом куске кода 

                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. Хм ... Может даже работать, хотя я бы так не поступил. Вы уверены, что ваш ввод правильный? Связан ли граф, т.е. действительно ли вершина достижима?

...