ใน ดีเอฟเอส โหนดที่กำลังสำรวจจะถูกจัดเก็บไว้ในโครงสร้างข้อมูลแบบสแตก ขอบที่นำเราไปยังโหนดที่ยังไม่ได้สำรวจเรียกว่า ‘ ขอบการค้นพบ ‘ ในขณะที่ขอบที่นำไปสู่โหนดที่เข้าชมแล้วจะถูกเรียกว่า ‘ ขอบบล็อก '. ดีเอฟเอส มีประโยชน์ในสถานการณ์เมื่อโปรแกรมเมอร์ต้องการค้นหาส่วนประกอบหรือวงจรที่เชื่อมต่อกันในกราฟ
ปฏิบัติตามหลักเกณฑ์ของบทความนี้เพื่อนำไปใช้ ดีเอฟเอส ใน C++
การใช้งาน DFS ใน C ++
ในหัวข้อต่อไปนี้ เราจะพูดถึงวิธีการ ดีเอฟเอส ถูกนำมาใช้ใน C ++ สามารถทำตามขั้นตอนที่กำหนดเพื่อนำไปใช้ ดีเอฟเอส .
- แทรกรูทโหนดของต้นไม้หรือกราฟลงในสแต็ก
- เพิ่มรายการบนสุดของสแต็กไปยังรายการที่คุณเยี่ยมชม
- ค้นหาโหนดที่อยู่ติดกันทั้งหมดไปยังโหนดที่เยี่ยมชมและเพิ่มโหนดที่ยังไม่ได้เยี่ยมชมสแต็ก
- ทำซ้ำขั้นตอนที่ 2 และ 3 จนกว่าสแต็กจะว่างเปล่า
DFS ซูโดโค้ด
เดอะ ดีเอฟเอส pseudocode แสดงไว้ด้านล่าง ใน ความร้อน() ฟังก์ชัน เราดำเนินการของเรา ดีเอฟเอส การทำงานในแต่ละโหนด เนื่องจากกราฟอาจมีสองส่วนที่ขาดการเชื่อมต่อ เราจึงสามารถเรียกใช้ ดีเอฟเอส อัลกอริทึมในแต่ละโหนดเพื่อให้แน่ใจว่าเราครอบคลุมทุกจุดยอด
ดีเอฟเอส ( ก )
ก. เยี่ยมชม = จริง
สำหรับ ทุก b ∈ g โฆษณา [ ก ]
ถ้า ข. เยี่ยมชม == เท็จ
ดีเอฟเอส ( ก.ข )
ความร้อน ( )
{
สำหรับทุกๆ ∈ g
ก. เยี่ยมชม = เท็จ
สำหรับทุกๆ ∈ g
ดีเอฟเอส ( ก )
}
ที่นี่ g, a และ b แสดงถึงกราฟ โหนดที่เข้าชมครั้งแรกและโหนดในสแต็กตามลำดับ
การใช้ DFS ใน C ++
โปรแกรม C++ สำหรับ ดีเอฟเอส การใช้งานได้รับด้านล่าง:
#รวม
#รวม<แผนที่>
#รวม<รายการ>
โดยใช้ เนมสเปซ มาตรฐาน ;
แม่แบบ < พิมพ์ชื่อ ที >
ระดับ ความลึกก่อนการค้นหา
{
ส่วนตัว :
แผนที่ < เสื้อรายการ < ที > > adjList ;
สาธารณะ :
ความลึกก่อนการค้นหา ( ) { }
เป็นโมฆะ Add_edge ( t a, t b, บูล คุณ = จริง )
{
adjList [ ก ] . push_back ( ข ) ;
ถ้า ( คุณ )
{
adjList [ ข ] . push_back ( ก ) ;
}
}
เป็นโมฆะ พิมพ์ ( )
{
สำหรับ ( อัตโนมัติ ฉัน : adjList ) {
ศาล << ฉัน. อันดับแรก << '->' ;
สำหรับ ( รายการที : ฉัน. ที่สอง ) {
ศาล << รายการ << ',' ;
}
ศาล << จบ ;
}
}
เป็นโมฆะ dfs_helper ( โหนดแผนที่ < เสื้อ บูล > & เยี่ยมชม ) {
เยี่ยมชม [ โหนด ] = จริง ;
ศาล << โหนด << ' ' << จบ ;
สำหรับ ( เพื่อนบ้าน : adjList [ โหนด ] ) {
ถ้า ( ! เยี่ยมชม [ เพื่อนบ้าน ] ) {
dfs_helper ( เพื่อนบ้านมาเยี่ยม ) ;
}
}
}
เป็นโมฆะ ดีเอฟเอส ( ที src )
{
แผนที่ < เสื้อ บูล > เยี่ยมชม ;
dfs_helper ( src,เยี่ยมชม ) ;
}
} ;
นานาชาติ หลัก ( ) {
ความลึกก่อนการค้นหา < นานาชาติ > ช ;
กรัม Add_edge ( 0 , 5 ) ;
กรัม Add_edge ( 0 , 7 ) ;
กรัม Add_edge ( 4 , 7 ) ;
กรัม Add_edge ( 7 , 8 ) ;
กรัม Add_edge ( 2 , 1 ) ;
กรัม Add_edge ( 0 , 6 ) ;
กรัม Add_edge ( 2 , 4 ) ;
กรัม Add_edge ( 3 , 2 ) ;
กรัม Add_edge ( 3 , 6 ) ;
กรัม Add_edge ( 7 , 5 ) ;
กรัม Add_edge ( 5 , 8 ) ;
กรัม พิมพ์ ( ) ;
กรัม ดีเอฟเอส ( 6 ) ;
ศาล << จบ ;
}
ในรหัสนี้เราได้ดำเนินการ ดีเอฟเอส อัลกอริทึมตามรหัสหลอกที่ให้ไว้ด้านบน เรามีโหนด 12 คู่ เรากำหนดคลาส “ ช ” ซึ่งแสดงถึงกราฟที่มีจุดยอด a และ b ซึ่งแสดงถึงโหนดที่เข้าชมและไม่ได้เยี่ยมชม
เอาต์พุต
บทสรุป
ดีเอฟเอส เป็นอัลกอริทึมการค้นหายอดนิยมที่มีประโยชน์สำหรับหลายสถานการณ์ เช่น การค้นหาวงจรในกราฟ และการรับข้อมูลเกี่ยวกับส่วนประกอบที่เชื่อมต่อหรือจุดยอดทั้งหมดในกราฟ นอกจากนี้เรายังอธิบายถึงการทำงานของ ดีเอฟเอส วิธีการด้วยตัวอย่าง ดีเอฟเอส ใช้สแต็คเพื่อดำเนินการเทคนิคและยังสามารถใช้กับต้นไม้