โปรแกรม C++ หา Maximum Cut ในกราฟ (Edge Connectivity)

การหา Maximum Cut ในกราฟ

โปรแกรมนี้หา Edge Connectivity ของกราฟ ซึ่งหมายถึงบริดจ์ (bridge) ที่ถ้าลบออกจะทำให้กราฟไม่ต่อเนื่อง จำนวนคอมโพเนนต์ที่เชื่อมต่อจะเพิ่มขึ้นเมื่อลบบริดจ์ในกราฟไม่เชื่อมต่อแบบไม่มีทิศทาง

ฟังก์ชันและ pseudocode

Begin
    ฟังก์ชัน connections() แบบ recursive หาการเชื่อมต่อ:
    A) ทำเครื่องหมายโหนดปัจจุบันว่า visited
    B) เริ่มต้นค่า time และ low
    C) วนลูปผ่านโหนดติดกันทั้งหมด
    D) ตรวจสอบว่า subtree ที่ rooted ที่ x มีการเชื่อมต่อกับ ancestor ของ w หรือไม่
       ถ้าจุดยอดต่ำสุดที่เข้าถึงได้จาก subtree ใต้ x อยู่ต่ำกว่า w ในต้นไม้ DFS แสดงว่า w-x เป็นการเชื่อมต่อ
    E) อัปเดตค่า low ของ w สำหรับ parent function calls
End

Begin
    ฟังก์ชัน Con() ใช้ connections():
    A) ทำเครื่องหมายโหนดทั้งหมดว่า unvisited
    B) เริ่มต้น par, visited, connections
    C) แสดงการเชื่อมต่อระหว่างเส้นขอบในกราฟ
End

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

#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);
    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]);
            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]) 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;
}

ผลลัพธ์

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