โปรแกรม C++ หาจุดศูนย์กลางการเชื่อมต่อของกราฟ (Vertex Connectivity)

การหาจุดศูนย์กลางการเชื่อมต่อของกราฟ

เพื่อหา Vertex Connectivity ต้องหาจุดข้อต่อ (Articulation Points) จุดข้อต่อคือจุดที่ถ้าลบออก (รวมเส้นขอบที่ผ่าน) จะทำให้กราฟไม่ต่อเนื่อง สำหรับกราฟไม่เชื่อมต่อแบบไม่มีทิศทาง จุดข้อต่อคือจุดที่การลบออกทำเพิ่มจำนวนคอมโพเนนต์ที่เชื่อมต่อ

อัลกอริทึม

Begin
    ใช้ DFS หาจุดข้อต่อ:
    ใน DFS จุดยอด w เป็นจุดข้อต่อถ้าเงื่อนไขใดเงื่อนไขหนึ่งเป็นจริง:
    1) w เป็นรากของต้นไม้ DFS และมีลูกอย่างน้อย 2 ตัว
    2) w ไม่ใช่ราก และมีลูก x ที่ไม่มีจุดยอดใน subtree ของ w มี back edge ไปยัง ancestor ของ w
End

ตัวอย่างโค้ด

#include <iostream>
#include <list>
#define N -1
using namespace std;

class G {
    int n;
    list<int> *adj;
    void APT(int v, bool visited[], int dis[], int low[], int par[], bool ap[]);
public:
    G(int n);
    void addEd(int w, int x);
    void AP();
};

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::APT(int w, bool visited[], int dis[], int low[], int par[], bool ap[]) {
    static int t = 0;
    int child = 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]) {
            child++;
            par[x] = w;
            APT(x, visited, dis, low, par, ap);
            low[w] = min(low[w], low[x]);
            if (par[w] == N && child > 1) ap[w] = true;
            if (par[w] != N && low[x] >= dis[w]) ap[w] = true;
        } else if (x != par[w]) low[w] = min(low[w], dis[x]);
    }
}

void G::AP() {
    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;
    }
    for (int i = 0; i < n; i++)
        if (!visited[i]) APT(i, visited, dis, low, par, ap);
    for (int i = 0; i < n; i++)
        if (ap[i]) 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;
}

ผลลัพธ์

Articulation points in first graph
0 2