cで深さの最初の検索を書きます

Question

Cで深さの最初の検索を作成しようとしています。すべての到達可能なノードのセットを維持する代わりに、頂点のisVisitedフィールドを訪問のために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;
}

この検索の問題は、ノードがたとえそうであっても到達可能であることを返さないことです。誰かが私がこれをどのように修正できるか知っていますか？

Answer 1

このコードで

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

何らかの理由で隣接する頂点を追加しています currentVertex->neighbors[i] DFSスタックに 2回. 。なぜあなたはそれを二度しているのですか？

さらに、最初の追加は、隣人がすでに訪問されているかどうかを確認することさえせずに行われます。なんで？そのようにして（つまり、既に訪問されているかどうかを確認せずに追加する）循環グラフで、アルゴリズムは無限のサイクルになります。同じサイクルの周りに永遠にループし、グラフの他の部分に到達することはありません。

PS if(currentVertex->isVisited == 0) その前にチェックすると、おそらく無限のループが発生するのを防ぐでしょうが、それでも上記の繰り返しの追加は私には意味がありません。

PPSああ、私はそれを手に入れ始めていると思います。意図的に2回追加されます。バックトラッキング用の最初の（無条件の）追加、フォワードDFSの進行のための2回目の追加（チェック付き）。うーん...私はそれをそのようにしませんが、うまくいくかもしれません。あなたの入力は正しいですか？グラフは接続されていますか？つまり、頂点は本当に到達可能ですか？