สะพานในกราฟ

ขอบในกราฟที่ไม่ระบุทิศทางจะเรียกว่าสะพานเชื่อม ถ้าเพียงเอาออก จะตัดการเชื่อมต่อกราฟ หรือสร้างองค์ประกอบต่างๆ ของกราฟ

ในทางปฏิบัติ หากมีบริดจ์บางส่วนอยู่ในเครือข่ายเมื่อการเชื่อมต่อของบริดจ์ขาด ก็สามารถทำลายเครือข่ายทั้งหมดได้

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

อินพุต:เมทริกซ์ที่อยู่ติดกันของกราฟ 0 1 1 1 01 0 1 0 01 1 0 0 01 0 0 0 0 10 0 0 1 0 เอาต์พุต:บริดจ์ในกราฟที่กำหนด:บริดจ์ 3--4บริดจ์ 0--3 
อัลกอริทึม
 
bridgeFind(เริ่ม, เข้าชม, ดิสก์, ต่ำ, พาเรนต์)
 

 อินพุต -  จุดยอดเริ่มต้น อาร์เรย์ที่เข้าชมเพื่อทำเครื่องหมายเมื่อมีการเยี่ยมชมโหนด แผ่นดิสก์จะเก็บเวลาการค้นพบของจุดยอด และระดับต่ำจะเก็บข้อมูลเกี่ยวกับทรีย่อย พาเรนต์จะถือพาเรนต์ของจุดยอดปัจจุบัน
 

 ผลลัพธ์ − พิมพ์หากพบสะพานใด ๆ
 
Begin time :=0 // ค่าของเวลาจะไม่ถูกกำหนดค่าเริ่มต้นสำหรับการเรียกใช้ฟังก์ชันถัดไป mark start เป็น set disc[start] ที่เยี่ยมชมแล้ว :=time+1 และ low[start] :=time + 1 time :=time + 1 สำหรับจุดยอด v ทั้งหมดในกราฟ G ให้ทำถ้ามีขอบอยู่ระหว่าง (เริ่ม, v) จากนั้นหากไปที่ v แล้ว parent[v] :=start bridgeFind(v, visit, disc, low, parent) low[start] :=ต่ำสุดของ low[start] และ low[v] if low[v]> disc[start] จากนั้นแสดงสะพานจากจุดเริ่มต้นไปยัง v อื่นหาก v ไม่ใช่พาเรนต์ของ start แล้ว low[start] :=ต่ำสุดของ low[start] และ disc[v] doneEnd
 
ตัวอย่าง
 
#include#define NODE 5using เนมสเปซ 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 " < 
ผลลัพธ์
 
บริดจ์ในกราฟที่กำหนด:บริดจ์ 3--4บริดจ์ 0--3