บทนำ
กราฟไม่มีทิศทางเรียกว่า Biconnected ถ้าระหว่างโหนดใดๆ มีเส้นทางที่ไม่ร่วมโหนด (Vertex-disjoint paths) อย่างน้อย 2 เส้นทาง กล่าวคือ มี Cycle ระหว่างโหนดคู่นั้น
เงื่อนไข: 1) กราฟเชื่อมต่อ (Connected) 2) ไม่มี Articulation Point (Cut Vertex) - โหนดที่ถ้าลบจะทำให้กราฟขาดการเชื่อมต่อ
ใช้ DFS หา Articulation Point และตรวจสอบว่าเยี่ยมครบทุกโหนดหรือไม่
อินพุตและเอาต์พุต
Input: เมทริกซ์ติดกัน 5x5 Output: The Graph is a biconnected graph.
อัลกอริทึม
isArticulation(start, visited, disc, low, parent)
Input: โหนดเริ่มต้น, visited, disc (discovery time), low (low link), parent
Output: True ถ้าพบ Articulation Point
Begin
time := 0 (static)
dfsChild := 0
mark start visited
disc[start] := low[start] := ++time
for โหนด v ใน G do
if มีเส้นขอบ (start, v) then
if v ไม่ visited then
dfsChild++
parent[v] := start
if isArticulation(v, visited, disc, low, parent) return true
low[start] := min(low[start], low[v])
if parent[start] == -1 AND dfsChild > 1 return true // Root มีลูก > 1
if parent[start] != -1 AND low[v] >= disc[start] return true
else if v != parent[start] then
low[start] := min(low[start], disc[v])
done
return false
End
isBiconnected(graph)
Input: กราฟ
Output: True ถ้าเป็น Biconnected
Begin
ตั้งค่า visited = false, parent = -1 สำหรับทุกโหนด
if isArticulation(0, visited, disc, low, parent) return false
for โหนด i ทุกตัว do if ไม่ visited return false done
return true
End
ตัวอย่างโค้ด (C++)
#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
int min(int a, int b) { return (a 1) return true;
if(parent[start] != -1 && low[v] >= disc[start]) return true;
} else if(v != parent[start]) {
low[start] = min(low[start], disc[v]);
}
}
}
return false;
}
bool isBiConnected() {
bool *vis = new bool[NODE];
int *disc = new int[NODE], *low = new int[NODE], *parent = new int[NODE];
for(int i = 0; i
ผลลัพธ์
The Graph is a biconnected graph.
