Tìm Cầu (Bridges) trong Đồ thị

Giới thiệu

Cạnh trong đồ thị vô hướng gọi là cầu (bridge) nếu xóa nó làm đồ thị không liên thông hoặc tách thành nhiều thành phần.

Trong mạng lưới, cầu là điểm yếu: đứt cầu thì mạng bị chia cắt.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề:
0 1 1 1 0
1 0 1 0 0
1 1 0 0 0
1 0 0 0 1
0 0 0 1 0
Đầu ra: Bridges in given graph:
Bridge 3--4
Bridge 0--3

Thuật toán

bridgeFind(start, visited, disc, low, parent)

Đầu vào: Đỉnh bắt đầu, mảng visited, disc (thời gian khám phá), low (thấp nhất có thể đạt), parent.

Đầu ra: In ra cầu nếu tìm thấy.

Begin
  time := 0  // static, không reset giữa các gọi đệ quy
  đánh dấu start đã thăm
  disc[start] := low[start] := ++time
  với mọi đỉnh v trong G làm:
    nếu có cạnh (start, v) thì
      nếu v chưa thăm thì
        parent[v] := start
        bridgeFind(v, visited, disc, low, parent)
        low[start] := min(low[start], low[v])
        nếu low[v] > disc[start] thì in cầu start--v
      ngược lại nếu v ≠ parent[start] thì
        low[start] := min(low[start], disc[v])
  done
End

Ví dụ (C++)

#include <iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
  {0, 1, 1, 1, 0},
  {1, 0, 1, 0, 0},
  {1, 1, 0, 0, 0},
  {1, 0, 0, 0, 1},
  {0, 0, 0, 1, 0}
};

int min(int a, int b) { return (a < b) ? a : b; }

void bridgeFind(int start, bool visited[], int disc[], int low[], int parent[]) {
  static int time = 0;
  visited[start] = true;
  disc[start] = low[start] = ++time;
  for(int v = 0; v < NODE; v++) {
    if(graph[start][v]) {
      if(!visited[v]) {
        parent[v] = start;
        bridgeFind(v, visited, disc, low, parent);
        low[start] = min(low[start], low[v]);
        if(low[v] > disc[start]) cout << "Bridge " << start << "--" << v << endl;
      } else if(v != parent[start]) {
        low[start] = min(low[start], disc[v]);
      }
    }
  }
}

bool bridges() {
  bool *vis = new bool[NODE];
  int *disc = new int[NODE], *low = new int[NODE], *parent = new int[NODE];
  for(int i = 0; i < NODE; i++) { vis[i] = false; parent[i] = -1; }
  for(int i = 0; i < NODE; i++) if(!vis[i]) bridgeFind(i, vis, disc, low, parent);
}

int main() {
  cout << "Bridges in given graph:" << endl;
  bridges();
}

Kết quả đầu ra

Bridges in given graph:
Bridge 3--4
Bridge 0--3