การอ่านกราฟ.. ว่ากันว่ากราฟทุกกราฟเป็นกราฟอะไซคลิกที่กำกับโดย DAG ของส่วนประกอบที่เชื่อมต่ออย่างแน่นหนา ดังนั้นเพื่อที่จะค้นหาส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาเหล่านี้ เราจำเป็นต้องค้นหาโหนดในส่วน sink ของกราฟ .. ตอนนี้เพื่ออธิบายเพิ่มเติมฉันต้องอธิบาย post no และ pre no ..
pre no :- การสั่งซื้อล่วงหน้าคือรายการจุดยอดตามลำดับที่มีการเยี่ยมชมครั้งแรกโดยอัลกอริธึมการค้นหาเชิงลึกก่อน ดังนั้นจึงเป็นหมายเลขก่อนหน้าที่สอดคล้องกัน
ในทำนองเดียวกัน post no :- postordering คือรายการของจุดยอดตามลำดับที่อัลกอริธึม DFS เข้าชมครั้งล่าสุด หมายเลขโพสต์ที่เกี่ยวข้อง
ตอนนี้โพสต์ที่สูงที่สุดให้โหนดต้นทาง (เข้าใจจริง) แต่ทำไมไม่เรียงลำดับที่เพิ่มขึ้นของโพสต์ไม่ให้มีส่วนจม?
ข้อสงสัยของฉันคือ:- ทำไมเราต้องกลับกราฟเพื่อค้นหา sinks ดังนั้นจึงค้นหาส่วนประกอบที่เชื่อมต่อกัน ทำไมไม่อยู่ในกราฟเดียวกันเราจึงเรียกใช้อัลโกตามลำดับโดยเพิ่มหมายเลขโพสต์ (เนื่องจากโพสต์ที่ต่ำที่สุดไม่มีอยู่ในองค์ประกอบที่เชื่อมต่ออ่างล้างจาน)
ทำไมเราต้องกลับกราฟ?
