โปรแกรม C++ หา Edge Connectivity ของกราฟ

ในโปรแกรมนี้ต้องหา Edge Connectivity ของกราฟ Edge Connectivity หมายถึงเป็น bridge การลบออกจะทำให้กราฟ disconnected จำนวน connected components เพิ่มขึ้นเมื่อลบ bridge ใน undirected graph ที่ disconnected

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

Begin
  Function connections() เป็น recursive function หาการเชื่อมต่อ:
    A) ทำเครื่องหมายโหนดปัจจุบันว่า unvisited
    B) เริ่มต้น time และ low value
    C) ไปผ่านโหนดติดกันทั้งหมด
    D) ตรวจสอบว่า subtree ที่ rooted at x มีการเชื่อมต่อกับ ancestors ของ w หรือไม่ ถ้า lowest vertex ที่ถึงได้จาก subtree ใต้ x อยู่ต่ำกว่า u ใน DFS tree แสดงว่า w-x มีการเชื่อมต่อ
    E) อัปเดต low value ของ w สำหรับ parent function calls
End
Begin
  Function 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] == 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;
}

ผลลัพธ์

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