Strong connectivity. Strong connect

Strong connectivity. Strong connectivity is an equivalence relation on the set of vertices:
Reflexive: Every vertex v is strongly connected to itself.
Symmetric: If v is strongly connected to w, then w is strongly connected to v.
Transitive: If v is strongly connected to w and w is strongly connected to x, then v is also strongly connected to x.
Strong connectivity partitions the vertices into equivalence classes, which we refer to as strong components for short. We seek to implement the following API:
API for strong components
Remarkably, KosarajuSharirSCC.java implements the API with just a few lines of code added to CC.java, as follows:
Given a digraph G, use DepthFirstOrder.java to compute the reverse postorder of its reverse, GR.
Run standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerical order.
All vertices reached on a call to the recursive dfs() from the constructor are in a strong component (!), so identify them as in CC.
Proposition. The Kosaraju-Sharir algorithm uses preprocessing time and space proportional to V + E to support constant-time strong connectivity queries in a digraph.
Transitive closure. The transitive closure of a digraph G is another digraph with the same set of vertices, but with an edge from v to w if and only if w is reachable from v in G.

ผลลัพธ์ (ไทย) 1:

การเชื่อมต่อแข็งแรง เชื่อมต่อที่แข็งแรงมีความสัมพันธ์เทียบเท่าชุดของจุดยอด:สะท้อนกลับ: ทุกจุดยอด v ขอเชื่อมต่อเองสมมาตร: ถ้า v ขอเชื่อมต่อกับ w แล้ว w ขอเชื่อมต่อกับ vสกรรมกริยา: ถ้า v ขอเชื่อมต่อกับ w และ w ขอเชื่อมต่อ x แล้ววียังขอเชื่อมต่อกับ xเชื่อมต่อแข็งแรงกั้นจุดยอดในระดับเทียบเท่า ซึ่งเราอ้างถึงเป็นส่วนประกอบที่แข็งแกร่งสำหรับระยะสั้น เราพยายามใช้ API ดังต่อไปนี้:API สำหรับส่วนประกอบที่แข็งแรงอย่างยิ่ง KosarajuSharirSCC.java ใช้ API มีเพียงไม่กี่บรรทัดของรหัสที่เพิ่ม CC.java เป็นดังนี้:ให้ทวิอักษร G ใช้ DepthFirstOrder.java เพื่อคำนวณ postorder ย้อนกลับของการย้อนกลับ GRเรียกใช้ DFS มาตรฐาน G ได้พิจารณาจุดยอดหมายในใบสั่งคำนวณเพียงใบตัวเลขมาตรฐานจุดยอดทั้งหมดแล้วการเรียก dfs() ซ้ำจากตัวสร้างที่อยู่ในส่วนประกอบที่แข็งแกร่ง (!) ให้ ระบุใน CCข้อเสนอการ อัลกอริทึม Kosaraju Sharir ใช้เวลาและพื้นที่เป็นสัดส่วนกับ V + E เบื้องเพื่อสนับสนุนการเชื่อมต่อแข็งแรงคงเวลาถามในไดกราฟการปิดสกรรมกริยา ไดกราฟ G เชิดสกรรมกริยาเป็นทวิอักษรอื่นที่ มีจุดยอดชุดเดียวกัน แต่ มีขอบจาก v กับ w ถ้าและเดียว w จะสามารถเข้าถึงจาก v ในกรัม

ผลลัพธ์ (ไทย) 2:

การเชื่อมต่อที่แข็งแกร่ง การเชื่อมต่อที่แข็งแกร่งเป็นเท่าเทียมกันความสัมพันธ์กับชุดของจุด:
สะท้อน: โวลต์จุดสุดยอดทุกคนจะถูกเชื่อมต่ออย่างยิ่งกับตัวเอง.
สมมาตร: ถ้าโวลต์มีการเชื่อมต่ออย่างยิ่งที่จะน้ำหนักแล้วน้ำหนักมีการเชื่อมต่ออย่างยิ่งที่จะ v.
สกรรมกริยา: ถ้าโวลต์มีการเชื่อมต่ออย่างยิ่งที่จะเ และน้ำหนักมีการเชื่อมต่ออย่างยิ่งที่จะ x แล้วโวลต์นอกจากนี้ยังมีการเชื่อมต่ออย่างยิ่งที่จะ x.
การเชื่อมต่อที่แข็งแกร่งพาร์ติชันจุดสมดุลในชั้นเรียนซึ่งเราหมายถึงส่วนประกอบที่แข็งแกร่งเป็นสำหรับระยะสั้น เราพยายามที่จะใช้ API ต่อไปนี้:
API
สำหรับส่วนประกอบที่แข็งแกร่งอย่างน่าทึ่งKosarajuSharirSCC.java ดำเนินการ API ที่มีเพียงไม่กี่บรรทัดของรหัสที่จะเพิ่ม CC.java
ดังนี้กำหนดเดี่ยวG, DepthFirstOrder.java ใช้เพื่อคำนวณ Postorder กลับ การย้อนกลับของ GR.
เรียก DFS มาตรฐานใน G แต่พิจารณาจุดป้ายเพื่อคำนวณเพียงแทนที่จะเป็นลำดับตัวเลขมาตรฐาน.
จุดทั้งหมดถึงการเรียกร้องให้ DFS recursive (ที่) จากคอนสตรัคอยู่ในองค์ประกอบที่แข็งแกร่ง ( !) เพื่อระบุตัวตนของพวกเขาในขณะที่ซีซี.
โจทย์ อัลกอริทึม Kosaraju-Sharir ใช้เวลาประมวลผลเบื้องต้นและพื้นที่สัดส่วนกับ V + E ที่จะสนับสนุนอย่างต่อเนื่องเวลาคำสั่งการเชื่อมต่อที่แข็งแกร่งในเดี่ยวได้.
ปิดสกรรมกริยา ปิดสกรรมกริยาของ G เป็นเดี่ยวเดี่ยวกับชุดเดียวกันของจุดอื่น แต่ที่มีขอบจาก v แรก w ถ้าหากน้ำหนักสามารถเข้าถึงได้จาก v ในกรัม

ผลลัพธ์ (ไทย) 3:

การเชื่อมต่อที่แข็งแกร่ง การเชื่อมต่อที่แข็งแกร่งมีความสัมพันธ์สมมูลบนเซตของจุดทุกจุดยอด v :
สะท้อนขอเชื่อมต่อกับตัวเอง .
สมมาตร : ถ้า V ขอเชื่อมต่อกับ w แล้ว w ขอเชื่อมต่อกับ V
V : ถ้าการขอเชื่อมต่อกับ W และ w ขอเชื่อมต่อกับ X , V ยังขอเชื่อมต่อกับ
xการเชื่อมต่อที่แข็งแกร่งในพาร์ทิชันจุดสมมูล คลาสที่เราดูเป็นองค์ประกอบที่แข็งแกร่งสำหรับสั้น เราพยายามที่จะใช้ API API สำหรับองค์ประกอบต่อไปนี้ :

แข็งแรงสุดๆ kosarajusharirscc.java ใช้ API ที่มีเพียงไม่กี่บรรทัดของรหัสเพิ่ม cc.java ดังนี้
ให้ไดกราฟ G ใช้ depthfirstorder.java คำนวณย้อนกลับ postorder ของ GR
ย้อนกลับวิ่งแบบมาตรฐานบนกรัม แต่ให้พิจารณาจุดที่ในการสั่งซื้อเพียงคำนวณแทนคำสั่งเชิงตัวเลขมาตรฐาน .
ทุกจุด ถึงเรียก recursive dfs() จากผู้สร้างเป็นองค์ประกอบที่แข็งแกร่ง ( ! ) เพื่อให้ระบุได้ใน CC .
ข้อเสนอการใช้ sharir โกสรชุขั้นตอนวิธีการเตรียมพื้นที่และเวลา ? 5 E คงสนับสนุนเวลาค้นหาในการเชื่อมต่อที่แข็งแกร่งทวิอักษร .
การปิดงาน การปิดของไดกราฟ G เป็นทวิอักษรอื่นกับชุดเดียวกันของจุด แต่ด้วยขอบจาก V W ถ้าและเพียงถ้า W สามารถเข้าถึงได้จาก 5 กรัม