Để tìm độ liên thông đỉnh của đồ thị cần tìm các Điểm khớp (Articulation Points) của đồ thị đó. Điểm khớp (Cut Vertices) trong đồ thị là đỉnh mà khi xóa nó (và các cạnh qua nó) sẽ làm đứt gãy đồ thị. Điểm khớp của đồ thị vô hướng không liên thông là đỉnh mà khi xóa sẽ làm tăng số thành phần liên thông.
Thuật toán
Begin Dùng DFS để tìm điểm khớp: Trong DFS, đỉnh w là điểm khớp nếu thỏa một trong hai điều kiện: 1) w là gốc của cây DFS và có ít nhất hai con. 2) w không phải gốc và có con x sao cho không đỉnh nào trong cây con gốc w có cạnh ngược đến tổ tiên của w. End
Ví dụ
#include<iostream> #include <list> #define N -1 using namespace std; class G { int n; list<int> *adj; //khai báo hàm void APT(int v, bool visited[], int dis[], int low[], int par[], bool ap[]); public: G(int n); //constructor void addEd(int w, int x); void AP(); }; 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::APT(int w, bool visited[], int dis[], int low[], int par[], bool ap[]) { static int t=0; int child = 0; //khởi tạo số con của cây DFS là 0. //đánh dấu nút hiện tại đã thăm visited[w] = true; dis[w] = low[w] = ++t; list<int>::iterator i; //Duyệt tất cả đỉnh kề for (i = adj[w].begin(); i != adj[w].end(); ++i) { int x = *i; //x là đỉnh kề hiện tại if (!visited[x]) { child++; par[x] = w; APT(x, visited, dis, low, par, ap); low[w] = min(low[w], low[x]); // w là điểm khớp trong các trường hợp sau: // w là gốc cây DFS và có hai hoặc nhiều con. if (par[w] == N && child> 1) ap[w] = true; // Nếu w không phải gốc và giá trị low của một con lớn hơn hoặc bằng giá trị discovery của w. if (par[w] != N && low[x] >= dis[w]) ap[w] = true; } else if (x != par[w]) //cập nhật giá trị low low[w] = min(low[w], dis[x]); } } void G::AP() { // Đá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]; bool *ap = new bool[n]; for (int i = 0; i < n; i++) { par[i] = N; visited[i] = false; ap[i] = false; } // Gọi APT() để tìm điểm khớp trong cây DFS gốc đỉnh 'i' for (int i = 0; i < n; i++) if (visited[i] == false) APT(i, visited, dis, low, par, ap); //in các điểm khớp for (int i = 0; i < n; i++) if (ap[i] == true) cout << i << " "; } int main() { cout << "\nArticulation points in first graph \n"; G g1(5); g1.addEd(1, 2); g1.addEd(3, 1); g1.addEd(0, 2); g1.addEd(2, 3); g1.addEd(0, 4); g1.AP(); return 0; }Kết quả
Articulation points in first graph 0 2