โปรแกรม C++ หาจุด Articulation Points ในกราฟ

Articulation Points (หรือ Cut Vertices) ในกราฟ คือจุดที่ถ้าลบออก (รวมขอบที่ผ่าน) จะทำให้กราฟ disconnected Articulation point สำหรับ undirected graph ที่ disconnected คือโหนดที่ถ้าลบออกจะเพิ่มจำนวน connected components

อัลกอริทึม

Begin
  ใช้ dfs หา articulation point:
  ใน DFS โหนด w เป็น articulation point ถ้าเงื่อนไขใดเงื่อนไขหนึ่งเป็นจริง:
  1) w เป็น root ของ DFS tree และมีลูกอย่างน้อย 2 ตัว
  2) w ไม่ใช่ root และมีลูก x ที่ไม่มีโหนดใน subtree rooted at w มี back edge ไป ancestors ของ 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] == false)
      APT(i, visited, dis, low, par, ap);
  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;
}

ผลลัพธ์

Articulation points in first graph
0 2