กราฟที่เชื่อมต่อแบบสองทาง

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

เราสามารถพูดได้ว่ากราฟ G เป็นกราฟที่มีการเชื่อมต่อแบบสองทางหากมีการเชื่อมต่อ และไม่มีจุดประกบหรือจุดยอดที่ตัดอยู่ในกราฟ

เพื่อแก้ปัญหานี้ เราจะใช้การข้ามผ่าน DFS โดยใช้ DFS เราจะพยายามค้นหาว่ามีจุดประกบอยู่หรือไม่ เรายังตรวจสอบด้วยว่า DFS เข้าเยี่ยมชมจุดยอดทั้งหมดหรือไม่ ถ้าไม่ เราสามารถพูดได้ว่ากราฟไม่ได้เชื่อมต่อ

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

Input:Adjacency matrix of the graph.0 1 1 1 01 0 1 0 01 1 0 0 11 0 0 0 10 0 1 1 0Output:กราฟเป็นกราฟที่มีการเชื่อมต่อสองทาง

อัลกอริทึม

เป็นข้อต่อ (เริ่ม, เข้าชม, ดิสก์, ต่ำ, ระดับบนสุด)

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

ผลลัพธ์ − เป็นจริงหากพบจุดประกบ

Begin time :=0 // ค่าของเวลาจะไม่ถูกเตรียมใช้งานสำหรับการเรียกใช้ฟังก์ชันถัดไป dfsChild :=0 ทำเครื่องหมาย start as เยี่ยมชม set disc[start] :=time+1 และ low[start] :=time + 1 เวลา :=เวลา + 1 สำหรับจุดยอด v ทั้งหมดในกราฟ G ให้ทำถ้ามีขอบระหว่าง (เริ่ม, v) จากนั้นหากมีการเยี่ยมชม v ให้เพิ่ม dfsChild parent[v] :=start if isArticulation(v, เยี่ยมชม , disc, low, parent) เป็นจริง จากนั้นคืนค่า ture low[start] :=ขั้นต่ำของ low[start] และ low[v] หาก parent[start] คือ φ AND dfsChild> 1 จากนั้นคืนค่า true หาก parent[start] คือ φ AND low[v]>=disc[start] จากนั้นคืนค่า true else ถ้า v ไม่ใช่ parent ของ start แล้ว low[start] :=ขั้นต่ำของ low[start] และ disc[v] เสร็จสิ้นแล้ว return falseEnd 

 isBiconnected(กราฟ) 
 

 ป้อนข้อมูล: กราฟที่กำหนด
 

 ผลลัพธ์ − เป็นจริงหากกราฟมีการเชื่อมต่อแบบสองทาง
 
เริ่มแรก ตั้งค่าจุดยอดทั้งหมดที่ไม่ได้เยี่ยมชม และพาเรนต์ของแต่ละจุดยอดคือ φ ถ้า isArticulation(0, เข้าชม, ดิสก์, ต่ำ, พาเรนต์) =จริง จากนั้นคืนค่าเท็จสำหรับแต่ละโหนด i ของกราฟ ทำถ้าฉันไม่ได้เยี่ยมชม จากนั้น return false done return trueEnd
 
ตัวอย่าง
 
#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 1) {// เมื่อคุณมีลูก 2 คนขึ้นไปคืนค่า true; } if(parent[start] !=-1 &&low[v]>=disc[start]) คืนค่าจริง; } else if(v !=parent[start]) // update low of start สำหรับการโทรก่อนหน้า low[start] =min(low[start], disc[v]); } } return false;}bool isBiConnected() { bool *vis =บูลใหม่[NODE]; int *disc =int ใหม่[NODE]; int *low =int ใหม่[NODE]; int *parent =ใหม่ int[NODE]; สำหรับ (int i =0; i 
ผลลัพธ์
 
กราฟเป็นกราฟที่เชื่อมโยงกัน