32

グラフで橋を見つけなければならないプログラミングタスク（宿題ではありません）があります。少し自分で取り組んだのですが、満足のいくものは思いつきませんでした。だから私はそれをグーグルで検索しました、私は何かを見つけました、しかしそれが提示されているので私はアルゴリズムを理解することができません。誰かがこのコードを見て、私に説明をお願いします。

public Bridge(Graph G) {
    low = new int[G.V()];
    pre = new int[G.V()];
    for (int v = 0; v < G.V(); v++) low[v] = -1;
    for (int v = 0; v < G.V(); v++) pre[v] = -1;

    for (int v = 0; v < G.V(); v++)
        if (pre[v] == -1)
            dfs(G, v, v);
}

public int components() { return bridges + 1; }

private void dfs(Graph G, int u, int v) {
    pre[v] = cnt++;
    low[v] = pre[v];
    for (int w : G.adj(v)) {
        if (pre[w] == -1) {
            dfs(G, v, w);
            low[v] = Math.min(low[v], low[w]);
            if (low[w] == pre[w]) {
                StdOut.println(v + "-" + w + " is a bridge");
                bridges++;
            }
        }

        // update low number - ignore reverse of edge leading to v
        else if (w != u)
            low[v] = Math.min(low[v], pre[w]);
    }
}
4

4 に答える 4

82

定義: ブリッジはエッジです。削除すると、グラフが切断されます (または、接続されているコンポーネントの数が 1 つ増えます)。

グラフの橋に関する 1 つの観察。ループに属するエッジはブリッジにはなりません。したがって、 のようなグラフでは、エッジのA--B--C--Aいずれかを削除しても、グラフが切断されることはありません。しかし、無向グラフの場合、エッジは次のことを意味します。そして、このエッジはまだブリッジである可能性があり、それが存在する唯一のループは です。したがって、バック エッジによって形成されるループのみを考慮する必要があります。ここで、関数の引数で渡した親情報が役立ちます。などのループを使用しないと役立ちます。A--BB--CC--AA--BB--AA--B--AA--B--A

バック エッジ (またはループ) を識別するために、および配列A--B--C--Aを使用します。配列は、dfs アルゴリズムの配列に似ています。ただし、頂点が訪問済みであるというフラグを立てるだけでなく、各頂点を (dfs ツリー内の位置に従って) 異なる番号で識別します。配列は、ループがあるかどうかを識別するのに役立ちます。配列は、現在の頂点が到達できる(配列からの) 最小番号の頂点を識別します。lowpreprevisitedlowlowpre

このグラフを見てみましょうA--B--C--D--B。

Aから始まる

dfs:   ^                 ^                 ^                 ^              ^
pre:   0 -1 -1 -1 -1  0--1 -1 -1  1  0--1--2 -1  1  0--1--2--3  1  0--1--2--3--1
graph: A--B--C--D--B  A--B--C--D--B  A--B--C--D--B  A--B--C--D--B  A--B--C--D--B
low:   0 -1 -1 -1 -1  0--1 -1 -1  1  0--1--2 -1  1  0--1--2--3  1  0--1--2--3->1

この時点で、グラフにサイクル/ループが発生しています。今回はコードif (pre[w] == -1)で false になります。したがって、else の部分に入ります。Bが の親頂点であるかどうかをチェックする if ステートメントがありDます。そうではないので、の値を にD吸収します。例を続けると、Bprelow

dfs:            ^
pre:   0--1--2--3
graph: A--B--C--D
low:   0--1--2--1

このlow値は、コードDを介して に伝播します。Clow[v] = Math.min(low[v], low[w]);

dfs:         ^           ^           ^
pre:   0--1--2--3--1  0--1--2--3--1  0--1--2--3--1
graph: A--B--C--D--B  A--B--C--D--B  A--B--C--D--B
low:   0--1--1--1--1  0--1--1--1--1  0--1--1--1--1

Aサイクル/ループが識別されたので、頂点がループの一部ではないことに注意してください。したがって、A--Bブリッジとして印刷します。コードlow['B'] == pre['B']は、エッジがBブリッジになることを意味します。これは、到達できる最も低い頂点BがBそれ自体であるためです。

この説明がお役に立てば幸いです。

于 2012-06-27T07:38:01.550 に答える
0

エッジ (c,d) が与えられ、それがブリッジであるかどうかを確認する必要があるとしましょう
。この問題を解決するにはいくつかの方法がありますが、1 つに集中しましょう。

  • c から始めて、BFSを実行する必要があります。
  • エッジ CD がある場合は、アクセスしないでください。
  • ブール値を訪問して、頂点を追跡します。

最後に、d がアクセスされていることがわかった場合、これは、cd を削除しても、ソース c から d をアクセスできることを意味します。したがって、cd はブリッジではありません。上記の短い実装は次のとおりです。

int isBridge(int V, ArrayList<ArrayList<Integer>> adj,int c,int d)
{
    Queue<Integer> q = new LinkedList<>();
    boolean visited[] = new boolean[V];
    ArrayList<Integer> ls = new ArrayList<>();
    
    q.add(c);
    
    while(!q.isEmpty()) {
        
        Integer v = q.remove();
        
        if(visited[v])
            continue;

        visited[v] = true;
        ls.add(v);
        
        for(Integer e: adj.get(v)) {
            
            if(visited[e] || (c == v && d == e))
                continue;
            q.add(e);
        }
    }
    
    if(visited[d] == true)
        return 0;
    return 1;
    
}
于 2021-05-10T12:07:37.490 に答える