DFS (Depth First Traversal) ในโครงสร้างข้อมูล: การสั่งซื้อและแอปพลิเคชันคืออะไร

ความหมายของ DFS ในโครงสร้างข้อมูล

DFS ในโครงสร้างข้อมูลหรือที่เรียกว่าการข้ามผ่านครั้งแรกในเชิงลึกเป็นอัลกอริธึมแบบเรียกซ้ำที่ใช้เป็นหลักในการค้นหาจุดยอดทั้งหมดของโครงสร้างข้อมูลกราฟหรือแผนภูมิ Traversal คือการเยี่ยมชมทุกโหนดของกราฟ อัลกอริธึมเริ่มต้นจากโหนดรูท (ซึ่งอาจเป็นโหนดใดก็ได้เช่นเดียวกับโหนดรูทในกราฟ) และไปไกลที่สุดเท่าที่จะสามารถทำได้ตามแต่ละสาขาก่อนที่จะย้อนกลับ

แนวคิดคือการเริ่มต้นจากโหนดรูทหรือโหนดโดยพลการและทำเครื่องหมายโหนดไว้ หลังจากนี้ คุณต้องย้ายไปยังโหนดที่อยู่ติดกันที่ไม่ได้ทำเครื่องหมายและดำเนินการวนซ้ำจนกว่าจะไม่มีโหนดที่อยู่ติดกันที่ไม่ได้ทำเครื่องหมาย จากนั้นย้อนรอยและตรวจสอบโหนดอื่นๆ ที่ไม่ได้ทำเครื่องหมายและสำรวจพวกมัน ขั้นตอนสุดท้ายคือการพิมพ์โหนดภายในเส้นทาง

อัลกอริทึม

กำหนดฟังก์ชันแบบเรียกซ้ำที่จะใช้ดัชนีของโหนดและอาร์เรย์ที่เข้าชม

1. ทำเครื่องหมายโหนดปัจจุบันว่าเยี่ยมชมแล้วจากนั้นพิมพ์
2. สำรวจบันทึกที่อยู่ติดกันทั้งหมดและบันทึกที่ไม่ได้ทำเครื่องหมาย แล้วเรียกใช้ฟังก์ชันแบบเรียกซ้ำด้วยดัชนีของโหนดที่อยู่ติดกัน

สำรวจหลักสูตรวิศวกรรมซอฟต์แวร์ยอดนิยมของเรา

คุณสมบัติ

การวิเคราะห์เวลาและพื้นที่ใน DFS ในโครงสร้างข้อมูลจะแตกต่างกันไปตามขอบเขตการใช้งาน ตามทฤษฎีแล้ว DFS ส่วนใหญ่จะใช้ข้ามกราฟเต็มและต้องใช้เวลา O(|V|+|E|) โดยที่ |V| แสดงจำนวนจุดยอดและ |E| แสดงถึงจำนวนขอบ กราฟนี้เป็นเส้นตรง

ในแอปพลิเคชันเหล่านี้ ช่องว่าง O(|V|) ยังถูกใช้เป็นทางเลือกสุดท้ายในการเก็บสแต็คของจุดยอดที่จัดเก็บไว้ในเส้นทางการค้นหาและชุดของจุดยอดที่เข้าชมแล้ว ดังนั้น การตั้งค่าขอบเขตเวลาและพื้นที่จึงคล้ายกับการค้นหาแบบกว้างก่อน ในที่นี้ อัลกอริธึมทั้งสองที่ใช้นั้นขึ้นอยู่กับความซับซ้อนน้อยกว่าและขึ้นอยู่กับลักษณะต่าง ๆ ของคำสั่งจุดยอดที่สร้างโดยอัลกอริทึมทั้งสอง

เมื่อพูดถึงแอปพลิเคชันของ DFS ในโครงสร้างข้อมูลที่เกี่ยวข้องกับโดเมนเฉพาะ เช่น การค้นหาโซลูชันในการรวบรวมข้อมูลเว็บหรือ AI กราฟที่ต้องมีการสำรวจข้อมูลอาจมีความสำคัญเกินกว่าจะเข้าชมได้ทั้งหมด ในกรณีเช่นนี้ การค้นหาจะดำเนินการในระดับความลึกที่จำกัดเท่านั้น เนื่องจากทรัพยากรมีจำกัด เช่น พื้นที่ดิสก์หรือหน่วยความจำ โครงสร้างข้อมูลโดยทั่วไปจะไม่ใช้เพื่อติดตามชุดของจุดยอดทั้งหมดที่เยี่ยมชมก่อนหน้านี้ การค้นหาที่ดำเนินการในระดับความลึกที่จำกัดยังคงทำให้เวลาเป็นเส้นตรงเมื่อพูดถึงหน่วยของขอบและจุดยอดที่ขยายออก

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

ในกรณีดังกล่าว DFS ยังหันไปใช้วิธีฮิวริสติกในการเลือกสาขาที่มีแนวโน้มดีกว่า สุดท้าย เมื่อไม่สามารถกำหนดขีดจำกัดความลึกที่เหมาะสมได้ DFS แบบเน้นย้ำเชิงลึกแบบวนซ้ำจะถูกนำมาใช้ซ้ำๆ ผ่านลำดับขีดจำกัดที่เพิ่มขึ้น

เรียนรู้ หลักสูตรการพัฒนาซอฟต์แวร์ ออนไลน์จากมหาวิทยาลัยชั้นนำของโลก รับโปรแกรม Executive PG โปรแกรมประกาศนียบัตรขั้นสูง หรือโปรแกรมปริญญาโท เพื่อติดตามอาชีพของคุณอย่างรวดเร็ว

อัลกอริธึมการค้นหาความลึกครั้งแรก

จุดยอดแต่ละอันของกราฟในการใช้งาน DFS มาตรฐานแบ่งออกเป็นสองประเภท:

1. ไม่ได้เยี่ยมชม
2. เยี่ยมชมแล้ว

อัลกอริธึมนี้ใช้เพื่อระบุจุดยอดแต่ละจุดและทำเครื่องหมายว่าเยี่ยมชมแล้ว และในขณะเดียวกันก็หลีกเลี่ยงวงจร

นี่คือวิธีการทำงานของอัลกอริทึม DFS:

1. วางจุดยอดใดๆ ของกราฟลงในสแต็ก
2. ควรเพิ่มรายการที่ด้านบนของสแต็กลงในรายการที่เข้าชม
3. ทำรายการโหนดที่อยู่ติดกันของจุดยอดนั้นและเพิ่มโหนดที่ไม่อยู่ในรายการที่เยี่ยมชมที่ด้านบนของสแต็ก
4. ทำซ้ำขั้นตอนก่อนหน้าต่อไปจนกว่าสแต็กจะว่างเปล่า

การสั่งซื้อ DFS

การ สั่งซื้อจุดยอด: มีสี่วิธีในการเรียงลำดับจุดยอดเป็นเส้นตรงของกราฟหรือต้นไม้ใน DFS:

1. รายการจุดยอดที่จัดเรียงวิธีที่พวกเขาเข้าชมครั้งแรกโดยอัลกอริธึม DFS เรียกว่าการสั่งซื้อล่วงหน้า เป็นวิธีที่กระชับเพื่ออธิบายความคืบหน้าของการค้นหา
2. รายการของจุดยอดในลำดับที่อัลกอริธึมเข้าชมครั้งสุดท้ายเรียกว่าการจัดลำดับภายหลัง
3. รายการจุดยอดในลำดับที่ตรงข้ามกับการเข้าชมครั้งแรกคือการสั่งซื้อล่วงหน้าแบบย้อนกลับ ดังนั้นจึงไม่ควรเข้าใจผิดว่าเป็นการสั่งซื้อทางไปรษณีย์
4. รายการจุดยอดในลำดับที่ตรงข้ามกับการเยี่ยมชมครั้งล่าสุดคือการจัดลำดับแบบย้อนกลับ ไม่ควรเข้าใจผิดว่าเป็นการสั่งซื้อล่วงหน้า

นอกจากนี้ยังมีการจัดลำดับและย้อนกลับตามลำดับสำหรับต้นไม้ไบนารี

Depth First Search หรือ DFS สำหรับกราฟ

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

ผลลัพธ์ของการค้นหาความลึกครั้งแรก

การค้นหาเชิงลึกเป็นอันดับแรกสามารถอธิบายได้ง่ายขึ้นในแง่ของต้นไม้ที่ทอดยาวของจุดยอดที่มีถึงในการค้นหาแล้ว ตามแผนผังขยายนี้ ขอบกราฟดั้งเดิมแบ่งออกเป็นสามประเภท: ขอบด้านหน้าที่โหนดของต้นไม้ชี้ไปทางลูกหลานคนหนึ่ง ขอบด้านหลังที่โหนดชี้ไปยังบรรพบุรุษคนหนึ่ง และขอบตัด ซึ่งไม่ทำหน้าที่ใด ๆ ก่อนหน้านี้

การประยุกต์ใช้ Depth First Traversal (DFS)

การค้นหาความลึกเป็นอันดับแรกใช้ในอัลกอริทึมต่อไปนี้เป็นส่วนประกอบหลัก:

• ค้นหาส่วนประกอบที่เชื่อมต่อ
• ค้นหาส่วนประกอบที่เชื่อมต่อ 2 (จุดยอดหรือขอบ)
• การหาสะพานของกราฟ
• การค้นหาส่วนประกอบที่เชื่อมต่อ 3 (จุดยอดหรือขอบ)
• การเรียงลำดับทอพอโลยี
• ค้นหาส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนา
• การค้นหาว่าสปีชีส์นั้นคล้ายกับสปีชีส์หนึ่งหรืออีกสปีชีส์ในต้นไม้สายวิวัฒนาการหรือไม่
• การทดสอบระนาบ
• การสร้างคำเพื่อกำหนดชุดขีด จำกัด ของกลุ่มใด ๆ
• ไขปริศนาที่มีทางออกเดียว เช่น เขาวงกต
• เขา วงกต gen eration
• ค้นหาสองการเชื่อมต่อในกราฟ

DFS Pseudocode และการใช้งานใน Python

ฟังก์ชัน init() ทำงานบนทุกโหนดใน pseudocode ด้านล่างเพื่อให้แน่ใจว่ามีการเยี่ยมชมจุดยอดทั้งหมด นี่เป็นสิ่งสำคัญอย่างยิ่งเนื่องจากกราฟอาจมีส่วนที่ไม่เชื่อมต่อกัน

นี่คือรหัสเทียม:

DFS(G, ยู)

u.visited = จริง

สำหรับแต่ละ v ∈ G.Adj[u]

ถ้า v.visited == false

DFS(G,v)

ในนั้น() {

สำหรับคุณ ∈ G

u.visited = เท็จ

สำหรับคุณ ∈ G

DFS(G, ยู)

}

นี่คือการใช้งาน DFS ใน Python:

กราฟ = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'7' : []

}

เยี่ยมชม = ชุด ()

def dfs(เยี่ยมชม, กราฟ, โหนด):

ถ้าโหนดไม่ได้เข้าเยี่ยมชม:

พิมพ์ (โหนด)

เยี่ยมชมเพิ่ม (โหนด)

สำหรับเพื่อนบ้านในกราฟ[โหนด]:

dfs(เยี่ยมชม, กราฟ, เพื่อนบ้าน)

พิมพ์ (“นี่คือ DFS:”)

dfs(เข้าชมแล้ว, กราฟ, '5')

เอาท์พุท:

นี่คือ DFS: 5

สำรวจหลักสูตรวิศวกรรมซอฟต์แวร์ยอดนิยมของเรา

ความซับซ้อนของ Depth First Search

John Reif สำรวจความซับซ้อนในการคำนวณของ Depth First Search เพื่อให้แม่นยำ ในกราฟ ข้อเท็จจริงที่กำหนดคือ G ให้ O เป็นลำดับมาตรฐานที่กำหนดโดยอัลกอริธึม DFS ที่ทำซ้ำ G แทนกราฟ และ O แทนผลลัพธ์การสั่งซื้อของอัลกอริธึม DFS ที่ซ้ำซ้อน ผลลัพธ์นี้เรียกว่าการจัดลำดับ DFS เกี่ยวกับพจนานุกรม

บทสรุป

เป้าหมายหลักของอัลกอริธึม DFS คือการเยี่ยมชมทุกจุดยอดที่หลีกเลี่ยงวงจรในกราฟเป้าหมาย หากคุณต้องการมีส่วนร่วมกับการดำเนินการค้นหาขั้นสูงหรือการดำเนินการสั่งซื้อ คุณควรพิจารณาดำเนินการตามหลักสูตรระดับพรีเมียมและแบบองค์รวมในการค้นหาเชิงลึกและโครงสร้างข้อมูล

upGrad มีหลักสูตร DFS ระดับแนวหน้า เช่น วิทยาศาสตรมหาบัณฑิตสาขาวิทยาการคอมพิวเตอร์ และ ความเชี่ยวชาญพิเศษ ด้าน Big Data

หากคุณกำลังดิ้นรนเพื่อก้าวต่อไปและมองหาคำแนะนำจากผู้เชี่ยวชาญ upGrad Mentorship พยายามที่จะจัดเซสชันแบบตัวต่อตัวกับที่ปรึกษาด้านอาชีพและผู้เชี่ยวชาญที่ดีที่สุดในอุตสาหกรรม