2

いくつかの条件が満たされるまでエッジを 1 つずつ削除するグラフ構造があります。私の脳は完全に停止しており、エッジを削除するとグラフが 2 つ以上のグラフに分割されるかどうかを効率的に検出する方法が見つかりません。

ブルートフォースの解決策は、ランダムなノードからすべてのノードに到達できるまでbfsを実行することですが、大きなグラフでは時間がかかりすぎます...

何か案は？

編集:少し検索した後、私がやろうとしていることは、エッジが「ブリッジ」であるかどうかを見つける必要があるフルーリーのアルゴリズムに非常に似ているようです。

4

3 に答える 3

1

削除するとグラフが切断されるエッジは「ブリッジ」と呼ばれます。O(|V|+|E|) で、グラフ全体に対する単一の深さ優先検索でそれらを見つけることができます。関連するアルゴリズムは、次のすべての「アーティキュレーション ポイント」(削除された場合にグラフを切断するノード) を見つけます。2 つのアーティキュレーション ポイント間のエッジはすべてブリッジです (2 回目のパスですべてのエッジをテストできます)。

//
// g: graph; v: current vertex id; 
// r_p: parents (r/w); r_a: ascents (r/w); r_ap: art. points, bool array (r/w)
// n_v: bfs order-of-visit 
//
void dfs_art_i(graph *g, int v, int *r_p, int *r_v, int *r_a, int *r_ap, int *n_v) {
    int i;
    r_v[v] = *n_v;
    r_a[v] = *n_v;
    (*n_v) ++;

    // printf("entering %d (nv = %d)\n", v, *n_v);
    for (i=0; i<g->vertices[v].n_edges; i++) {
        int w = g->vertices[v].edges[i].target;
        // printf("\t evaluating %d->%d: ", v, w);
        if (r_v[w] == -1) {    
            // printf("...\n");
            // This is the first time we find this vertex
            r_p[w] = v;
            dfs_art_i(g, w, r_p, r_v, r_a, r_ap, n_v);
            // printf("\n\t ... back in %d->%d", v, w);
            if (r_a[w] >= r_v[v]) {
                // printf(" - a[%d] %d >= v[%d] %d", w, r_a[w], v, r_v[v]);
                // Articulation point found
                r_ap[i] = 1;
            }
            if (r_a[w] < r_a[v]) {
                // printf(" - a[%d] %d < a[%d] %d", w, r_a[w], v, r_a[v]);
                r_a[v] = r_a[w];
            }
            // printf("\n");
        }
        else {
            // printf("back");
            // We have already found this vertex before
            if (r_v[w] < r_a[v]) {
                // printf(" - updating ascent to %d", r_v[w]);
                r_a[v] = r_v[w];
            }
            // printf("\n");
        }
    }
}

int dfs_art(graph *g, int root, int *r_p, int *r_v, int *r_a, int *r_ap) {
    int i, n_visited = 0, n_root_children = 0;
    for (i=0; i<g->n_vertices; i++) {
        r_p[i] = r_v[i] = r_a[i] = -1;
        r_ap[i] = 0;
    }
    dfs_art_i(g, root, r_p, r_v, r_a, r_ap, &n_visitados);    

    // the root can only be an AP if it has more than 1 child
    for (i=0; i<g->n_vertices; i++) {
        if (r_p[i] == root) {
            n_root_children ++;
        }
    }
    r_ap[root] = n_root_children > 1 ? 1 : 0;
    return 1;
}
于 2011-06-16T06:38:16.290 に答える
0

削除するエッジをどのように選択しますか? 問題のドメインについて詳しく教えてください。

あなたのグラフはどのくらいの大きさですか？多分BFSは大丈夫です！

エッジが橋であるかどうかを調べようとしていると書いた後、中間性の測定値が小さい順にエッジを削除することをお勧めします。

基本的に、中間性は、グラフ内のエッジ (または頂点) の中心性の尺度です。中間性の値が高いエッジは、グラフのブリッジになる可能性が高くなります。

Webで調べてみると、アルゴリズムは「Girvan-Newmanアルゴリズム」と呼ばれています。

于 2009-10-14T15:18:28.877 に答える
0

頂点 A と B の間のリンクを削除すると、エッジの削除後も B から A に到達できることを確認できませんか? これは、ランダムなノードからすべてのノードに到達するよりも少し優れています。

于 2009-10-14T15:20:20.560 に答える