Chương trình này tìm độ liên thông cạnh (Edge Connectivity) của đồ thị. Một cạnh là cầu (bridge) nếu xóa nó làm đồ thị không liên thông. Số thành phần liên thông tăng khi xóa cầu trong đồ thị vô hướng không liên thông.
Các hàm và mã giả:
Bắt đầu
Hàm connections() đệ quy tìm kết nối:
A) Đánh dấu nút hiện tại đã thăm.
B) Khởi tạo time và low value.
C) Duyệt tất cả đỉnh kề.
D) Kiểm tra nếu cây con gốc x có kết nối đến tổ tiên của w.
Nếu đỉnh thấp nhất đạt được từ cây con dưới x nằm dưới u trong cây DFS,
thì w-x là cầu.
E) Cập nhật low value của w cho lời gọi cha.
Kết thúc
Bắt đầu
Hàm Con() dùng connections():
A) Đánh dấu tất cả đỉnh chưa thăm.
B) Khởi tạo parent, visited, connections.
C) In các cầu (connections) giữa các cạnh.
Kết thúc
Ví dụ mã nguồn
#include <iostream>
#include <list>
#define N -1
using namespace std;
class G {
int n;
list<int> *adj;
void connections(int n, bool visited[], int disc[], int low[], int par[]);
public:
G(int n); // constructor
void addEd(int w, int x);
void Con();
};
G::G(int n) {
this->n = n;
adj = new list<int>[n];
}
void G::addEd(int w, int x) {
adj[x].push_back(w);
adj[w].push_back(x);
}
void G::connections(int w, bool visited[], int dis[], int low[], int par[]) {
static int t = 0;
visited[w] = true;
dis[w] = low[w] = ++t;
list<int>::iterator i;
for (i = adj[w].begin(); i != adj[w].end(); ++i) {
int x = *i;
if (!visited[x]) {
par[x] = w;
connections(x, visited, dis, low, par);
low[w] = min(low[w], low[x]);
// Nếu đỉnh thấp nhất từ cây con x lớn hơn thời gian khám phá w, thì w-x là cầu
if (low[x] > dis[w])
cout << w << " " << x << endl;
} else if (x != par[w])
low[w] = min(low[w], dis[x]);
}
}
void G::Con() {
bool *visited = new bool[n];
int *dis = new int[n];
int *low = new int[n];
int *par = new int[n];
for (int i = 0; i < n; i++) {
par[i] = N;
visited[i] = false;
}
for (int i = 0; i < n; i++)
if (visited[i] == false)
connections(i, visited, dis, low, par);
}
int main() {
cout << "\nCác cầu (connections) trong đồ thị đầu tiên \n";
G g1(5);
g1.addEd(1, 2);
g1.addEd(3, 2);
g1.addEd(2, 1);
g1.addEd(0, 1);
g1.addEd(1, 4);
g1.Con();
return 0;
}
Kết quả
Các cầu (connections) trong đồ thị đầu tiên 2 3 1 2 1 4 0 1