Cầu trong đồ thị được kết nối

Question

Tôi có nhiệm vụ lập trình (không phải bài tập về nhà.) Nơi tôi phải tìm các cây cầu trong biểu đồ. Tôi đã làm việc trên nó một chút bản thân mình, nhưng không thể đưa ra bất cứ điều gì thỏa đáng. Vì vậy, tôi googled nó, tôi đã tìm thấy một cái gì đó nhưng tôi không thể hiểu các thuật toán như nó được trình bày. Ai đó có thể vui lòng xem mã này và cho tôi một lời giải thích.?

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]); 
    } 
} 

Answer 1

Def: Cầu là một cạnh, khi bị xóa, sẽ ngắt kết nối biểu đồ (hoặc tăng số thành phần được kết nối thêm 1).

Một quan sát về cầu trong biểu đồ; không có cạnh nào thuộc về vòng lặp có thể là cầu nối. Vì vậy, trong biểu đồ như A--B--C--A, hãy xóa bất kỳ cạnh nào A--B, B--C và C--A sẽ không ngắt kết nối biểu đồ. Tuy nhiên, đối với một đồ thị không được chiếu, cạnh A--B ngụ ý B--A; và cạnh này vẫn có thể là một cây cầu, nơi vòng lặp duy nhất nó nằm ở là A--B--A. Vì vậy, chúng ta nên xem xét chỉ những vòng được hình thành bởi một cạnh sau. Đây là nơi thông tin cha mẹ bạn đã truyền trong đối số hàm giúp. Nó sẽ giúp bạn không sử dụng các vòng lặp như A--B--A.

Bây giờ để xác định cạnh sau (hoặc vòng lặp), A--B--C--A, chúng tôi sử dụng các mảng low và pre. Mảng pre giống như mảng visited trong thuật toán dfs; nhưng thay vì chỉ gắn cờ rằng đỉnh như đã truy cập, chúng tôi xác định mỗi đỉnh bằng một số khác (theo vị trí của nó trong cây dfs). Mảng low giúp xác định xem có vòng lặp hay không. Mảng low xác định đỉnh được đánh số thấp nhất (từ pre) mà đỉnh hiện tại có thể tiếp cận.

Cho phép làm việc thông qua biểu đồ này A--B--C--D--B.

Bắt đầu tại 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 

Tại thời điểm này, bạn đã gặp phải một chu kỳ/vòng lặp trong biểu đồ. Trong mã của bạn if (pre[w] == -1) sẽ là sai thời gian này. Vì vậy, bạn sẽ nhập phần khác. Câu lệnh if có kiểm tra nếu B là đỉnh mẹ của D. Nó không phải là, vì vậy D sẽ hấp thụ B 's pre giá trị vào low. Tiếp tục ví dụ,

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

này giá trị low của D truyền lại C qua mã low[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 

Bây giờ, chu trình/vòng lặp được xác định, chúng tôi lưu ý rằng đỉnh A không phải là một phần của vòng lặp. Vì vậy, bạn in ra A--B làm cầu nối. Mã số low['B'] == pre['B'] có nghĩa là một cạnh để B sẽ là một cây cầu. Điều này là do, đỉnh thấp nhất mà chúng tôi có thể đạt được từ số B chính là số B.

Hy vọng lời giải thích này sẽ hữu ích.

Answer 2

Không phải là câu trả lời mới, nhưng tôi cần điều này bằng Python.Dưới đây là một bản dịch của các thuật toán cho một đối tượng NetworkX Graph vô hướng G:

def bridge_dfs(G,u,v,cnt,low,pre,bridges): 
    cnt += 1 
    pre[v] = cnt 
    low[v] = pre[v] 

    for w in nx.neighbors(G,v): 
     if (pre[w] == -1): 
      bridge_dfs(G,v,w,cnt,low,pre,bridges) 

      low[v] = min(low[v], low[w]) 
      if (low[w] == pre[w]): 
       bridges.append((v,w)) 

     elif (w != u): 
      low[v] = min(low[v], pre[w]) 

def get_bridges(G): 
    bridges = [] 
    cnt  = 0 
    low  = {n:-1 for n in G.nodes()} 
    pre  = low.copy() 

    for n in G.nodes(): 
     bridge_dfs(G, n, n, cnt, low, pre, bridges) 

    return bridges # <- List of (node-node) tuples for all bridges in G 

Cẩn thận với giới hạn độ sâu đệ quy Python cho đồ thị lớn ...

Answer 3

Không phải là một câu trả lời mới, nhưng tôi cần này cho JVM/Kotlin. Đây là bản dịch dựa trên com.google.common.graph.Graph.

/** 
* [T] The type of key held in the [graph]. 
*/ 
private class BridgeComputer<T>(private val graph: ImmutableGraph<T>) { 
    /** 
    * Counter. 
    */ 
    private var count = 0 
    /** 
    * `low[v]` = Lowest preorder of any vertex connected to `v`. 
    */ 
    private val low: MutableMap<T, Int> = 
     graph.nodes().map { it to -1 }.toMap(mutableMapOf()) 
    /** 
    * `pre[v]` = Order in which [depthFirstSearch] examines `v`. 
    */ 
    private val pre: MutableMap<T, Int> = 
     graph.nodes().map { it to -1 }.toMap(mutableMapOf()) 

    private val foundBridges = mutableSetOf<Pair<T, T>>() 

    init { 
     graph.nodes().forEach { v -> 
      // DO NOT PRE-FILTER! 
      if (pre[v] == -1) { 
       depthFirstSearch(v, v) 
      } 
     } 
    } 

    private fun depthFirstSearch(u: T, v: T) { 
     pre[v] = count++ 
     low[v] = checkNotNull(pre[v]) { "pre[v]" } 
     graph.adjacentNodes(v).forEach { w -> 
      if (pre[w] == -1) { 
       depthFirstSearch(v, w) 
       low[v] = 
        Math.min(checkNotNull(low[v]) { "low[v]" }, checkNotNull(low[w]) { "low[w]" }) 
       if (low[w] == pre[w]) { 
        println("$v - $w is a bridge") 
        foundBridges += (v to w) 
       } 
      } else if (w != u) { 
       low[v] = 
        Math.min(checkNotNull(low[v]) { "low[v]" }, checkNotNull(pre[w]) { "pre[w]" }) 
      } 
     } 
    } 

    /** 
    * Holds the computed bridges. 
    */ 
    fun bridges() = ImmutableSet.copyOf(foundBridges)!! 
} 

Hy vọng điều này giúp cuộc sống của người khác dễ dàng hơn.