1

例えば。1->2, 2->3, 3->4, 4->2, 2, 3, 4 を印刷したい.この頂点を取得しませんが、うまく機能しません。無限ループに陥ることもあります。

dfs を実行します。

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

DFS:

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
        printCycle(ver[v].to[i]);
}

および印刷サイクル:

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

int p = ver[v].p;

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

    p = ver[p].p;
}

printf("\n");

頂点構造体:

int *to; // neighbor list

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

2 に答える 2

1

「強く接続されたコンポーネント」を探しているようです-運が良ければ、グラフでこれらを見つけるためのよく知られたアルゴリズムがあります。タージャンを参照してください。

アルゴリズムはその記事でかなり詳しく説明されていますが、少し長くなってしまったので、ここには貼り付けません。また、研究目的でこれを行っているのでない限り、おそらく既存の実装を使用した方がよいでしょう。実装するのはそれほど難しくありませんが、それほど簡単でもありません。

編集。この質問は実際にはだまされているようです...これを言うのは苦痛ですが、おそらく閉じる必要があります。申し訳ありません。有向グラフでサイクルを検出するための最適なアルゴリズムを参照してください。

于 2012-05-03T08:58:42.973 に答える
0

DFS での無限ループを回避するには、頂点カラーリングを使用する必要があります。最初はすべての頂点が WHITE としてマークされています。初めて頂点を発見したとき (白としてマークされています)、それをグレーとしてマークする必要があります。GRAY 頂点を発見した場合、ループが見つかります。

于 2012-05-03T10:02:32.787 に答える