Depth First Search (DFS)

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

การท่องทรี/กราฟ

  • กระบวนการเข้าถึงทุกโหนด
  • Depth first search (DFS)
  • Breadth first search (BFS)
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - ไบนารีทรี

  • In-order
  • Pre-order
  • Post-order
โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left
โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current
โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order

  • ลำดับ: Left -> Current -> Right

ภาพแสดงการท่องแบบ In-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ In-order - การนำไปใช้

  • ลำดับ: Left -> Current -> Right
def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

ภาพแสดง binary search tree

  • ความซับซ้อน: $O(n)$
    • $n$ -> จำนวนโหนด
โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current
โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left
โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order

  • ลำดับ: Current -> Left -> Right

ภาพแสดงการท่องแบบ Pre-order บน binary search tree

โครงสร้างข้อมูลและอัลกอริทึมใน Python

การท่องแบบ Pre-order - การนำไปใช้

  • ลำดับ: Root -> Left -> Right
  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

ภาพแสดง binary search tree

  • ความซับซ้อน: $O(n)$
    • $n$ -> จำนวนโหนด
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Post-order

  • ลำดับ: Left
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Post-order

  • ลำดับ: Left -> Right
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Post-order

  • ลำดับ: Left -> Right -> Current

  • ความซับซ้อน: $O(n)$

    • $n$ -> จำนวนโหนด
โครงสร้างข้อมูลและอัลกอริทึมใน Python

เมื่อไหร่ควรใช้ in-order, pre-order และ post-order

  • in-order

    • ใช้ BST เพื่อดึงค่าโหนดตามลำดับจากน้อยไปมาก

  • pre-order

    • สร้างสำเนาของทรี
    • ได้ prefix expression

  • post-order

    • ลบไบนารีทรี
    • ได้ postfix expression
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

  • กราฟอาจมีวงจร (cycle)
    • ต้องติดตาม vertex ที่เข้าชมแล้ว
  • ขั้นตอน:
    1. เริ่มที่ vertex ใดก็ได้
    2. บันทึก vertex ปัจจุบันลงในรายการที่เข้าชมแล้ว
    3. สำหรับแต่ละ adjacent vertex ของโหนดปัจจุบัน
      • ถ้าเข้าชมแล้ว -> ข้ามไป
      • ถ้ายังไม่เข้าชม -> รัน DFS แบบ recursive
โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - กราฟ

ภาพแสดงการทำ depth first search บนกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Depth first search - การนำไปใช้

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)
  • ความซับซ้อน: $O(V+E)$
    • $V$ -> จำนวน vertex
    • $E$ -> จำนวน edge
โครงสร้างข้อมูลและอัลกอริทึมใน Python

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Preparing Video For Download...