0

グラフのサイクルを頂点のグループに置き換えようとしています(このサイクルを削除し、最大数の頂点を1回配置します)

struct group {
    int master; // representative of cycle
};

struct vertex {
    int *to; // neighbor list

    int nb; // how many neighbor
    int p; // parent
    short v; // was visited? 0 = false, 1 = true

    struct group *cycle; // is part of cycle? NULL = no, else pointer to group
};

各頂点でdfsを実行しています

void searchCycles() {
    int i;
    for (i = 0; i < MAX_VER; i += 1)
        if (ver[i].v == 0 && ver[i].nb > 0)
            dfs(i);
}

DFS:

void dfs(int v) {
    ver[v].v = 1;

    int i;
    for (i = 0; i < ver[v].nb; i += 1) {
        ver[ver[v].to[i]].p = v;

        if (ver[ver[v].to[i]].v == 0)
            dfs(ver[v].to[i]);
        else
                    // cycle found
            replaceCycle(ver[v].to[i]);
    }
}

関数を置き換え、どの頂点が循環しているかを出力します

void replaceCycle(int v) {
    struct group *g = &gr[usedGroup++];
    g->master = -1;

    printf("\nCYKL: %d ", v);

    int p = ver[v].p;

    while (p != v) {
        printf("%d(%d) ", p, v);

        p = ver[p].p;
    }

    printf("\n");
}

通常は動作しますが、無限ループになることがあります。私はそれをデバッグしようとしましたが、2 つ以上のサイクルがある場合、親 (頂点構造体の p) が失われます。これは正常に動作することを意味しますが、番号が間違っています。私はCとアルゴリズムを学んでいるので、あまり知りません。

これは宿題じゃない、スポイ問題だ

4

1 に答える 1

1

サイクルを交換したら、dfsを再起動します。

基本的に、訪問済みフラグは最初のサイクルに設定される可能性がありますが、2番目のサイクルをテストするためにそれをクリアする必要があります。（そして3番目、4番目など）

于 2012-05-02T18:16:06.617 に答える