Tính Liên Thông - Tuoitrekthc

1. Tìm thành phần liên thông trên đồ thị vô hướng

Định nghĩa. Cho đồ thị vô hướng G(V, E). Một thành phần liên thông của G là tập U gồm tối đa các đỉnh của V mà mọi cặp đỉnh bất kỳ của U đều tồn tại đường đi. Nếu G chỉ có một thành phần liên thông thì gọi G là đồ thị liên thông.

Thuật toán 1. Trong khi duyệt thăm mọi đỉnh, mỗi lần gọi BFS(i) hoặc DFS(i) là bắt đầu một thành phần liên thông chứa i:

int main() {

    . . .;    // Đọc input, xây dựng danh sách kề bằng 2 mảng adj[M] và head[N]

    time = 0; stplt=0;

    for (int i=0; i<N; i++) vao[i]=0; // Khởi trị  các đỉnh chưa thăm tới

    for (int i=0; i<N; i++) if (vao[i]==0){

         stplt++;

         cout<< “thành phần lthông thứ “ << stplt << “ gồm: “;

         BFS(i); // Trong hàm này thêm lệnh xuất ra các đỉnh của một thành phần lthông

    }

    return 0;

}

Thuật toán 2 (Hợp nhất cây).

Phương pháp hợp nhất cây để tìm vùng liên thông trên đồ thị vô hướng G(V, E):

Mỗi cây được đại diện bởi gốc của nó (vì khi biết gốc, có thể duyệt tìm các nút trong cây). Quy ước gốc của cây được gắn với một trọng số âm là w mà |w| bằng số nút trong cây, còn mỗi nút khác gốc được gắn với một trọng số dương là số hiệu đỉnh của nút gốc.

Ban đầu mỗi đỉnh i (“i=1, 2,…, n) được coi là một cây có duy nhất một nút là i làm gốc với trọng số là w(i)= -1. Sau đó thực hiện:

Vòng lặp { duyệt lần lượt mọi cạnh (x, y) thuộc E.

Nếu 2 đỉnh x, y của cạnh thuộc hai cây có gốc khác nhau là r­1 và   r2

(x thuộc cây có gốc r1, y thuộc cây có gốc r2) thì hợp nhất hai cây này như sau :

+ Đặt s = w(r1) + w(r2).

+ Nếu |w(r1)|<|w(r2)| (số nút trong cây r1 ít hơn số nút trong cây r2) thì chọn gốc của cây hợp nhất là r2. Do đó gán cho r2 trọng số là s và các nút trong cây gốc r1 gán  trọng số là r2 (coi như cây có gốc r1 được nạp thêm vào cây có gốc r2)

+ Nếu |w(r1)|>|w(r2)| chọn gốc của cây hợp nhất là r1. Do đó gán cho r1 trọng số s  và các nút trong cây gốc r2 gán trọng số r1  (cây có gốc r2 được nạp vào cây gốc r1)

} Lặp cho đến khi duyệt hết các cạnh.

Ví dụ. Chương trình sau đây cho biết số vùng liên thông trong đồ thị vô hướng và liệt kê các đỉnh trong từng vùng.

Dữ liệu vào lấy từ tệp tplt.in: Dòng đầu là số đỉnh của đồ thị. Các dòng sau, mỗi dòng hai số i và j thể hiện có cạnh (i; j).

Kết quả ra ghi vào tệp tplt.out: Dòng đầu tiên ghi số sv là số thành phần liên thông. Sv dòng sau, mỗi dòng ghi các đỉnh của cùng một vùng liên thông khác nhau.

Ví dụ

tplt.in	tplt.out
1 2 1 4 2 3 3 4 5 6 6 7	2 1 2 3 4 5 6 7

#include <iostream>

#include <fstream>

#define maxN 5000

using namespace std;

ifstream fi (“tplt.inp”);

ofstream fo (“tplt.out”);

int N, w[maxN], sv;

int find_root(int x){

    int i=x;

    while (w[i]>0) i=w[i];

    return i;

}

void change(int x, int y){

     //nap cay goc x vao cay goc y

     for (int i=1; i<=N; i++)

     if (w[i]==x) w[i]=y;

}

void union_(int x, int y) {

     int s = w[x]+w[y];

     if (w[x]>w[y]) {

         w[x]=y;

         change(x,y);

         w[y]=s;

     } else {

         w[y]=x;

         change(y,x);

         w[x]=s;

     }

}

void process(){

     int r1, r2, x, y;

     fi >> N;

     for (int i=1; i<=N; i++) w[i]=-1;

     while (fi>> x >> y) {

           r1 = find_root(x);

           r2 = find_root(y);

           if (r1!=r2) union_(r1,r2);

     }

}

void write_output(){

     for (int i=1; i<=N; i++)

          if (w[i]<0) sv++;

     fo << sv << endl;

    

     for (int i=1; i<=N; i++)

        if (w[i]<0) {

           fo << i << ” “;

           for (int j=1; j<=N; j++)

           if (w[j]==i) fo << j << ” “;

           fo << endl;

        }

}

int main() {

    process();

    write_output();

}        

2. Tìm thành phần liên thông mạnh trên đồ thị có hướng.

Định nghĩa 1. Cho đồ thị có hướng G(V, E). Một thành phần liên thông mạnh của G là tập U gồm tối đa các đỉnh của V mà mọi cặp đỉnh (i;j) bất kỳ của U đều tồn tại đường đi từ i tới j và đường đi từ j tới i. Nếu G chỉ có một thành phần liên thông mạnh thì gọi G là đồ thị liên thông mạnh.

Một đồ thị có hướng là liên thông yếu nếu thay các cung bằng cạnh được đồ thị vô hướng liên thông.

Định nghĩa 2. Các cung được duyệt qua trong quá trình duyệt theo DFS trên đồ thị tạo thành một cây gọi là cây tìm kiếm DFS.

Định nghĩa 3. Mỗi cung (u; v) được duyệt qua trong quá trình duyệt theo DFS gọi là một cung của cây DFS (hay gọi tắt là cung DFS), u là nút cha, v là nút con. Các nút được duyệt qua từ lúc bắt đầu thăm u đến khi thăm xong u (tìm kiếm chiều sâu từ u kết thúc) tạo thành một nhánh con của cây DFS (gốc của nhánh con này là u)

Định nghĩa 4. Trên cây DFS, các nút trong nhánh con gốc u gọi là các nút hậu duệ của u và ngược lại u là tiền bối của các nút này.

Định nghĩa 5. Trên đồ thị có hướng G, ngoài những cung DFS, còn có 3 loại cung sau đây không thuộc cây DFS:

• Cung xuôi (u, v) nếu u là tiền bối của v
• Cung ngược (u,v) nếu v là tiền bối của u
• Cung chéo (u,v) nếu v thuộc nhánh DFS đã duyệt trước u

Định lý 1 (điều kiện cần). Với mỗi thành phần liên thông mạnh C  luôn tồn tại một đỉnh r thuộc C sao cho mọi đỉnh của C đều thuộc nhánh cây DFS gốc r. Đỉnh r như vậy gọi là chốt của thành phần liên thông mạnh C.

Định lý 2 (điều kiện đủ). Với một chốt r không là tiền bối của bất kỳ chốt nào khác thì các đỉnh thuộc nhánh DFS gốc r chính là một thành phần liên thông mạnh

Định lý 3. Đỉnh r là chốt khi và chỉ khi nếu đỉnh r đã duyệt xong thì trên G không có cung ngược/cung chéo từ một nút của nhánh DFS gốc r tới nút được thăm trước r

 Thuật toán Tarjan tìm các thành phần liên thông mạnh (tìm kiếm theo chiều sâu).

Ý tưởng:

Lặp {

          + Chọn chốt r không là tiền bối của chốt nào khác.

+ Xuất thành phần liên thông mạnh gồm các nút thuộc nhánh DFS có gốc là r

+ Loại bỏ các nút thuộc nhánh DFS có gốc là r khỏi cây DFS

} cho đến khi hết các nút trên cây DFS.

Cài đặt:

Dùng mảng Number[N] đánh số thứ tự các đỉnh theo thứ tự duyệt đến: Number[u] là thứ tự duyệt đến đỉnh u. Đồng thời dùng mảng Low[N] để kết hợp với mảng Number[N] nhằm xác định chốt của một thành phần liên thông (đó là chốt không là tiền bối của chốt khác). Khi thăm tới đỉnh u, Low[u] được tính như sau: Xét các cung (u;v) thuộc đồ thị G,

+ Nếu v đã thăm thì Low[u]=Min{Low[u], Number[v].

+ Nếu v chưa thăm, gọi DFS(v), thăm xong v thì gán Low[u]=Min[Low[u], Low[v]}

Sau khi thăm xong u so sánh Number[u] và Low[u], nếu Low[u]≥Number[u] thì u là chốt của một thành phần liên thông gồm các nút trong nhánh DFS đỉnh u.

Mặt khác, ta dùng một Ngăn xếp S để tổ chức cây DFS. Các đỉnh từ khi duyệt đến u cho đến khi duyệt xong u lần lượt được đẩy vào ngăn xếp S. Nếu u là chốt thì lấy khỏi S các đỉnh từ đỉnh ngăn xếp S cho tới khi lấy ra u, đó chính là các đỉnh thuộc một thành phần liên thông mạnh đã được loại bỏ khỏi cây DFS.

Sau đây là chương trình cụ thể (tệp input dòng đầu ghi 2 số N và M tương ứng là số đỉnh và số cạnh của đồ thị G; M dòng tiếp theo, mỗi dòng ghi 2 số: x và y thể hiện có cung (x; y). Tệp output: Dòng đầu ghi số Scc là số thành phần liên thông mạnh, mỗi dòng tiếp theo trong Scc dòng ghi các đỉnh thuộc một vùng liên thông mạnh.)

#include <iostream>

#include <fstream>

#include <stack>

#define maxN 100000

#define maxM 1000000

using namespace std;

ifstream fi (“tarjan.inp”);

ofstream fo (“tarjan.out”);

stack<int> S;

int N, M, count_,Scc;

struct Te {int x, y;} e[maxM];

int link[maxM], head[maxN], Number[maxN], Low[maxN];

bool avail[maxN];

void read_input(){

     fi >> N >> M;

     for (int i=1; i<=M; i++) { // Đọc các cung và tạo danh sách liên thuộc

         fi >> e[i].x >> e[i].y;

         link[i] = head[e[i].x]; // Nạp e[i] vào danh sách các cung liên thuộc ra khỏi e[i].x

         head[e[i].x] = i;

     }

}

void init() {

     for (int i=1; i<=N; i++) avail[i]=true; // Chưa đỉnh nào bị loại

     count_=0; // Khởi trị biến đếm thứ tự duyệt đến

     Scc=0;    // Khởi trị số thành phần liên thông mạnh

     S.empty();// Khởi trị ngăn xếp

}

int min2(int x, int y) {

    if (x<y) return x; else return y;

}

void DFS(int u) { // Duyệt chiều sâu, xây dựng cây DFS và thực hiện thuật toán Tarjan

     int i, v;

     count_ ++; // Thứ tự duyệt đến của u

     Number[u]=count_; // Giá trị Number của u là thứ tự duyệt đến của u

     Low[u]=maxN + 1; // Khởi trị Low[u]

     S.push(u); // Nạp u vào ngăn xếp

     i = head[u]; // Số hiệu cung liên thuộc đi ra từ u

     while (i>0) {

           v=e[i].y; // v là đỉnh cuối của cung liên thuộc đi ra từ u

           if (avail[v]) // v chưa bị loại

              if (Number[v]!=0) // v đã thăm

                   Low[u]=min2(Low[u], Number[v]);

              else { // v chưa thăm

                   DFS(v); // duyệt từ v

                                            // đã duyệt xong v

                   Low[u]=min2(Low[u], Low[v]);

              }

           i = link[i]; // số hiệu cung liên thuộc tiếp theo đi ra từ u

     }

     if (Low[u]>= Number[u]) { // u là chốt của một thành phần liên thông mạnh

           Scc++; // tăng biến đếm số thành phần liên thông mạnh

           do {  // Lấy ra khỏi ngăn xếp các đỉnh thuộc thành phần liên thông mạnh này

               v = S.top(); S.pop ();

               fo << v << ” “;

               avail[v] = false;

           } while (v!=u); // Lấy cho đến khi lấy được u

           fo << endl;

     }

}

void process() {

     for (int i=1; i<=N; i++)

     if (avail[i]) DFS(i); //Nếu đỉnh i chưa bị loại thì thăm tiếp từ i để tìm các tplt mạnh

}     

int main() {

     read_input();

     init();

     process();  

     return 0;

}

Chia sẻ:

• X
• Facebook

Thích Đang tải...