การหา Bridge ในกราฟ (Bridges in a Graph)

บทนำ

เส้นขอบ (Edge) ในกราฟไม่มีทิศทางเรียกว่า Bridge ถ้าการลบมันทำให้กราฟไม่เชื่อมต่อ (Disconnected) หรือแยกเป็น Component หลายส่วน ในเครือข่ายจริง หาก Bridge ขาด จะทำให้เครือข่ายขาดหาย

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกัน 5x5
Output: Bridges in given graph:
        Bridge 3--4
        Bridge 0--3

อัลกอริทึม

bridgeFind(start, visited, disc, low, parent)

Input: โหนดเริ่มต้น, visited array, disc = discovery time, low = low link value, parent array
Output: พิมพ์ Bridge ที่พบ

Begin
    time := 0 (static, ไม่ reset ระหว่าง recursion)
    mark start visited
    disc[start] := low[start] := ++time
    for โหนด v ทุกตัวใน G do
        if มีเส้นขอบ (start, v) then
            if v ไม่ visited then
                parent[v] := start
                bridgeFind(v, visited, disc, low, parent)
                low[start] := min(low[start], low[v])
                if low[v] > disc[start] then แสดง Bridge start--v
            else if v != parent[start] then
                low[start] := min(low[start], disc[v])
    done
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 disc[start]) cout << "Bridge " << start << "--" << v << endl;
            } else if(v != parent[start]) {
                low[start] = min(low[start], disc[v]);
            }
        }
    }
}

bool bridges() {
    bool *vis = new bool[NODE];
    int *disc = new int[NODE];
    int *low = new int[NODE];
    int *parent = new int[NODE];
    for(int i = 0; i

ผลลัพธ์
Bridges in given graph:
Bridge 3--4
Bridge 0--3