Chương trình C++ tìm số cạnh tối thiểu cần cắt để làm đứt gãy đồ thị

Trong chương trình này cần tìm độ liên thông cạnh (Edge Connectivity) của đồ thị. Độ liên thông cạnh nghĩa là cầu (bridge), xóa nó thì đồ thị bị đứt gãy. 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.

Hàm và mã giả

Begin    Hàm connections() là hàm đệ quy tìm kết nối:    A) Đánh dấu nút hiện tại chưa thăm.    B) Khởi tạo thời gian và giá trị low    C) Duyệt tất cả đỉnh kề    D) Kiểm tra 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ây con dưới x nằm dưới u trong cây DFS, thì w-x là kết nối.    E) Cập nhật giá trị low của w cho lời gọi hàm cha. End

Hàm và mã giả của Con()

Begin    Hàm Con() dùng connections():    A) Đánh dấu tất cả đỉnh chưa thăm.    B) Khởi tạo par, visited, connections.    C) In các kết nối giữa các cạnh trong đồ thị. End

Ví dụ

#include<iostream> #include <list> #define N -1 using namespace std; class G {    //khai báo hàm    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]; } //thêm cạnh vào đồ thị void G::addEd(int w, int x) {    adj[x].push_back(w); //thêm u vào danh sách v    adj[w].push_back(x); //thêm v vào danh sách u } void G::connections(int w, bool visited[], int dis[], int low[], int par[]) {    static int t = 0;    //đánh dấu nút hiện tại đã thăm    visited[w] = true;    dis[w] = low[w] = ++t;    //Duyệt tất cả đỉnh kề    list<int>::iterator i;    for (i = adj[w].begin(); i != adj[w].end(); ++i) {       int x = *i; //x là đỉnh kề hiện tạ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 dưới x nằm dưới w trong cây DFS, thì w-x là kết nối          if (low[x] > dis[w])             cout << w << " " << x << endl;       }       else if (x != par[w])          low[w] = min(low[w], dis[x]);    } } void G::Con() {    // Đánh dấu tất cả đỉnh chưa thăm    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;    }    //gọi connections() tìm kết nối cạnh    for (int i = 0; i < n; i++)       if (visited[i] == false)          connections(i, visited, dis, low, par); } int main() {    cout << "\nConnections in first graph \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ả

Connections in first graph 2 3 1 2 1 4 0 1