การค้นหาในแนวลึกก่อน

การค้นหาแบบลึกก่อน(Depth first search)[]

รูปที่ 1 ลําดับการเดินทางบนโหนดของการค้นหาแบบลึกก่อนบนโครงสร้างต้นไม้

การค้นหาแบบลึกก่อน(Depth first search) (DFS) เป็นการค้นหาที่กําหนดทิศทางจากรูปของโครงสร้างต้นไม้ ที่เริ่มต้นจากโหนดราก(Root node) ที่อยู่บนสุด แล้วเดินลงมาให้ลึกที่สุด เมื่อถึงโหนดล่างสุด(Terminal node) ให้ย้อนขึ้นมาที่จุดสูงสุดของกิ่งเดี่ยวกันที่มีกิ่งแยกและยังไม่ได้เดินผ่าน แล้วเริ่มเดินลงจนถึงโหนดลึกสุดอีก ทําเช่นนี้สลับไปเรื่อยจนพบโหนดที่ต้องการหาหรือสํารวจครบทุกโหนดแล้วตามรูปที่ 1 การค้นหาแบบลึกก่อนจะมีลําดับการเดิน ตามโหนดดังตัวเลขที่กํากับไว้ในแต่ละโหนด.

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

การสํารวจจะเริ่มต้นที่ A และนําโหนดข้างเคียง B และ C มาเก็บไว้ในแสต็ก เมื่อสํารวจ Aเสร็จพอพข้อมูลจากแสต็กออกมาได้ C ทําการสํารวจ C และนําโหนดข้างเคียงกับ C ที่ยังไม่ได้ทําการสํารวจและยังไม่ได้อยู่ในแสต็กมาใส่แสต็ก D และ F พุช(Push) ใส่แสต็ก ดังนั้นในแสต็กตอนนี้มี B D F อยู่ เมื่อสํารวจ C เสร็จ พอพ F ออกมาทําการสํารวจ แล้วนําโหนดข้างเคียงที่ยังไม่ได้สํารวจและยังไม่ได้อยู่ในแสต็กมาใส่แสต็ก ซึ่งก็คือ G ดังนั้นข้อมูลในแสต็กจะเป็น B D G ทํ าเช่นนี้ไปเรื่อย ๆ จนจบการทํางานก็จะได้ลําดับการสํารวจคือ (A C F G H E D B) ตามตาราง 1 ดังต่อไปนี้

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

orderings Vertex[]

การค้นหาแบบลึกก่อนมีสามวิธีทั่วไปคือ

• Preordering คือรายการของการจุดที่เป็นจุดเริ่มในการค้นหาแบบลึกก่อน. นี้เป็นวิธีที่กะทัดรัดและเป็นธรรมชาติในการอธิบายความคืบหน้าของการค้นหา การPreordering ของต้นไม้ได้แสดงออกมาใน Polish notation.

• Postordering คือรายการของการจุดที่เป็นจุดสุดท้ายหรือครั้งล่าสุดในการค้นหาแบบลึกก่อน. Postordering ของ ต้นไม้ได้แสดงออกมาใน reverse Polish notation.

• Postordering reverse เป็น reverse ของ postordering เช่นรายการจุดตามลำดับตรงข้ามของการเข้าชมครั้งล่าสุด. เมื่อเริ่มค้นหาในกราฟแบบต้นไม้, postordering reverse จะเหมือนกับ preordering แต่โดยทั่วไปจะแตกต่างกันเมื่อค้นหากราฟธรรมดา. เช่นการค้นหากราฟโดยตรง

เริ่มต้นที่โหนดA ทางที่ไปอาจจะเป็นไปได้ทั้ง ABDBACA หรือ ACDCABA (ขึ้นกับขั้นตอนวิธีเลือกที่จะไป B หรือ C ในครั้งแรก). เมื่อถึงจุดสุดท้ายก็จะมีการ backtracking กลับไปยังโหนดก่อนหน้า ให้โหนดตรวจสอบเพื่อนบ้าน หากมี unvisitedอยู่ (แม้ว่าจะพบว่าไม่มี). ก็จะ preorderings ไป ABDC และ ACDB (ลำดับขึ้นกับการเลือกในขั้นต้น) ขณะที่ postorderings กลับไปเป็น ACBD และ ABCD (ลำดับขึ้นกับการเลือกในขั้นต้น). Reverse postordering ก็จะสร้าง topological ของการเรียงลำดับของกราฟโดยตรง. สิ่งนี้ยังมีประโยชน์ใน การควบคุมการไหล ซึ่งมักจะเป็น การควบคุมการไหลของธรรมชาติ กราฟข้างต้นอาจหมายถึงการคงบคุมการไหลซึ่งเขียนได้ในรูป

     if (A) then {
       B
     } else {
       C
     }
     D

และเป็นธรรมชาติที่จะต้องพิจารณาในการ ABCD หรือ ACBD แต่ไม่ธรรมชาติเมื่อใช้เพื่อ ABDC หรือ ACDB.

การดำเนินงาน[]

แบบมี recursive :

   def dfs(v, visited = None, 
       preorder_process  = lambda x: None,
       postorder_process = lambda x: None):
   if visited is None: visited = set()
   visited.add(v)
   preorder_process(v)
   for neighbor in v.neighbors:
       if neighbor not in visited:
           dfs(neighbor, visited, 
               preorder_process, 
               postorder_process)
   postorder_process(v)

แบบไม่มี recursion:

  def dfs(root, visited = None, 
       preorder_process  = lambda x: None):
   """
   Given a starting vertex, root, do a depth-first search.
   """
   from collections import deque
   to_visit = deque()
   if visited is None: visited = set()
  
   to_visit.append(root) # Start with root
   while len(to_visit) != 0:
       v = to_visit.pop()
       if v not in visited:
           visited.add(v)
           preorder_process(v)
           to_visit.extend(v.neighbors)

โปรแกรมประยุกต์[]

กลไกที่ DFS ใช้:

• ค้นหา ชิ้นส่วนเชื่อมต่อ.

• เรียงลำดับTopological.

• ค้นหา 2 - (ขอบหรือจุดสุดยอด) เพื่อเชื่อมต่อองค์ประกอบ.

• ค้นหา ชิ้นส่วนที่เชื่อมต่อกันอย่างแข็งแรง.

• แก้ปริศนาที่มีเพียงหนึ่งวิธีเช่น เขาวงกต (DFS สามารถปรับเพื่อหาวิธีการแก้ปัญหาทั้งหมดเพื่อเขาวงกตโดยรวมโหนดเฉพาะในเส้นทางปัจจุบันในการค้นหา.)

คำที่เกี่ยวข้อง[]

• Depth-limited search

• Dijkstra's algorithm

• Floyd–Warshall algorithm

• Hill climbing

• Iterative deepening depth-first search

• Johnson's algorithm

• Lexicographic breadth-first search

• Uniform-cost search

อ้างอิง[]

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp.540–549.

• Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed., Boston: Addison-Wesley, ISBN 0-201-89683-4, OCLC 155842391