ค้นหาเส้นทางอย่างโปร ด้วย BFS และ DFS ใน Python!!!

Mint Z — Sun, 06 Apr 2025 14:34:27 +0000

ในยุคนี้ที่อะไร ๆ ก็ต้องเร็ว ต้องฉลาดและต้องหาให้เจอภายในพริบตา อัลกอริธึมการค้นหา (Search Algorithms) ก็กลายเป็นพระเอกที่อยู่เบื้องหลังหลายสิ่งรอบตัวเราโดยไม่รู้ตัว ไม่ว่าจะเป็นแอปนำทางที่พาเราเลี่ยงรถติดเช่น Google Maps เกมแข่งรถที่บอทรู้ทางลัดเช่น Forza Horizon

บทความนี้จะพาคุณไปรู้จักกับสองตัวท็อปของวงการค้นหาอย่าง Breadth-First Search (BFS) และ Depth-First Search (DFS) ผ่านตัวอย่างในภาษา Python ที่อ่านง่าย ใช้งานได้จริงกัน

Breadth-First Search (BFS) คืออะไร?

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

ลองนึกถึงการค้นหาหมายเลขโทรศัพท์ของเพื่อนในสมุดโทรศัพท์ คุณอาจไล่ดูรายชื่อจากตัวอักษร A ไป B แล้วไป C ซึ่งคล้ายกับแนวคิดของ BFS หรือหากคุณอยู่ในห้องสมุดแล้วต้องการหาหนังสือที่ต้องการ คุณอาจเริ่มจากการดูหมวดหมู่หลักก่อน แล้วค่อยลงลึกไปยังชั้นที่เฉพาะเจาะจงมากขึ้น

ถ้างั้นเราลองมาดูตัวอย่างโค้ดกัน

ขั้นตอนที่1 การกำหนดกราฟในรูปแบบ Dictionary

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

ขั้นตอนที่2 ลองใช้งาน BFS

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

visited = []
queue = []

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    m = queue.pop(0) 
    print (m, end = " ") 

    for neighbour in graph[m]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("BFS")
bfs(visited, graph, 'A')

โดยโค้ดแต่ละส่วนจะมีการทำงานดังนี้ :

visited → ใช้เก็บว่าเคยไปเยี่ยมชมโหนดไหนแล้วบ้าง
queue → คิวที่ใช้เก็บโหนดที่ต้องไปต่อ
pop(0) → เป็นการดึงโหนดแรกเข้ามาทำงาน

ทีนี้ลองมาดูผลลัพธ์กันจากโค้ดเบื้องต้นกัน :

ผลลัพธ์จากการรันฟังก์ชัน BFS จะเป็นการแสดงโหนดที่ถูกเยี่ยมชมในลำดับที่กว้างที่สุดเป็นชั้น ๆ ชั้นหนึ่งแล้วไปยังระดับชั้นถัดไป โดยเริ่มจากโหนด ('A') และเยี่ยมชมโหนดที่เชื่อมต่อกับโหนดนั้นๆ ทีละระดับโดยใช้คิวในการจัดลำดับการเยี่ยมชมหรือก็คือมาก่อนได้ก่อนนั่นเอง
การทำงานของ BFS คือ:
เริ่มจาก 'A' และไปเยี่ยมชม 'B' และ 'C' (ที่อยู่ในระดับเดียวกันหรือชั้นเดียวกัน)
จากนั้นไปเยี่ยมชม 'D', 'E', และ 'F' ตามลำดับ

Depth-First Search (DFS) คืออะไร?

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

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

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

เราลองมาดูตัวอย่างโค้ดกัน

ขั้นตอนที่3 ลองใช้งาน DFS

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

visited = set()

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

print("DFS :")
dfs(visited, graph, 'A')

โดยโค้ดแต่ละส่วนจะมีการทำงานดังนี้ :

visited → ใช้เก็บว่าเคยไปเยี่ยมชมโหนดไหนแล้วบ้าง
dfs() → เป็นการค้นหาลึกเข้าไปเรื่อย ๆ จนสุดทางก่อนค่อยย้อนกลับ

ทีนี้ลองมาดูผลลัพธ์กันจากโค้ดเบื้องต้นกัน :

ผลลัพธ์ที่ได้จากการรันโค้ด DFS (Depth-First Search) คือการแสดงลำดับของโหนดที่ถูกเยี่ยมชม โดย DFS จะเลือก “ดำดิ่ง” ไปยังโหนดที่ลึกที่สุดก่อน แล้วค่อยย้อนกลับมาเก็บโหนดที่ยังตกค้างอยู่ภายหลัง

มาดูขั้นตอนแบบง่าย ๆ:

เริ่มจากโหนด 'A' → DFS จะเยี่ยมชม 'A' และมุ่งหน้าไปยัง 'B' เพราะเป็นโหนดที่เชื่อมต่อกับ 'A' เป็นลำดับแรก

จาก 'B' → ไปต่อที่ 'D' (ลึกสุดก่อนตามแนวทางของ DFS)

พอถึง 'D' → ไม่มีโหนดให้ไปต่อแล้ว → จึง “ย้อนกลับ” มาที่ 'B' แล้วไปยัง 'E'

เยี่ยมชม 'E' เสร็จ → กลับไปที่ 'A' อีกครั้ง

ตอนนี้ยังเหลือ 'C' ที่เชื่อมกับ 'A' → DFS เลยไปต่อที่ 'C'

จาก 'C' → เดินหน้าต่อไปยัง 'F'

สุดท้าย เยี่ยมชม 'F' เสร็จ → ย้อนกลับขึ้นมาเรื่อย ๆ จนครบทุกโหนดที่เชื่อมต่อ

ถ้าพูดง่าย ๆ คือ DFS จะเป็นการ “ลุยลึกก่อนคิดทีหลัง” คือไปให้สุดทางก่อน แล้วค่อยย้อนกลับมาเช็กว่าเรายังตกหล่นอะไรไว้บ้าง

ทีนี้เรามาดูตัวอย่างอื่นอีกกันโดยใช้เกมหนีซอมบี้กันบ้างดีกว่า

โดยก่อนเริ่มให้เรารันโค้ดนี้ลงไปใน Google Colab

import time
from collections import deque
import os

maze = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

player_pos = (0, 0)
zombie_pos = (4, 4)

def bfs(start, goal):
    queue = deque([[start]])
    visited = set()

    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if (x, y) == goal:
            return path

        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < 5 and 0 <= ny < 5 and maze[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append(path + [(nx, ny)])
                visited.add((nx, ny))
    return []

def print_maze(player, zombie):
    os.system('cls' if os.name == 'nt' else 'clear')
    for i in range(5):
        row = ""
        for j in range(5):
            if (i, j) == player:
                row += "P "
            elif (i, j) == zombie:
                row += "Z "
            elif maze[i][j] == 1:
                row += "# "
            else:
                row += ". "
        print(row)
    print()

while True:
    print_maze(player_pos, zombie_pos)

    if zombie_pos == player_pos:
        print("ผีจับคุณได้แล้ว! Game Over.")
        break

    move = input("WASD เพื่อขยับ: ").upper()
    dx, dy = 0, 0
    if move == "W": dx, dy = -1, 0
    elif move == "S": dx, dy = 1, 0
    elif move == "A": dx, dy = 0, -1
    elif move == "D": dx, dy = 0, 1

    new_x = player_pos[0] + dx
    new_y = player_pos[1] + dy

    if 0 <= new_x < 5 and 0 <= new_y < 5 and maze[new_x][new_y] == 0:
        player_pos = (new_x, new_y)

    path = bfs(zombie_pos, player_pos)
    if len(path) > 1:
        zombie_pos = path[1]

    time.sleep(0.1)

โดยโค้ดแต่ละส่วนจะมีการทำงานดังนี้ :

visited → ใช้เก็บว่าเคยไปเยี่ยมชมโหนดไหนแล้วบ้าง
queue → คิวที่ใช้เก็บโหนดที่ต้องไปต่อ
pop(0) → เป็นการดึงโหนดแรกเข้ามาทำงาน
bfs → ฟังก์ชันที่ใช้ค้นหาเส้นทางจากตำแหน่งผีไปยังตำแหน่งผู้เล่น โดยจะเริ่มต้นจากตำแหน่งของผีและตรวจสอบไปในทิศทางต่าง ๆ
print_maze → ฟังก์ชันที่ใช้แสดงผลแผนที่ทุกครั้งหลังจากที่ผู้เล่นหรือผีทำการขยับ

โดยหลักการเกมนี้มีง่าย ๆ คือ :

ซอมบี้จะเดินตามทางสั้นที่สุดโดยใช้ BFS
ผู้เล่นควบคุมด้วยปุ่ม W A S D
ผีจะเดินทีละ 1 ช่องทุกตา สลับกับเรา

เมื่อเราลองรันแล้วจะได้หน้าตา Output ออกมาเป็นแบบนี้

โดยให้เราเดินโดยใช้ปุ่มที่ตั้งค่าในโค้ดซึ่งในตัวอย่างนี้ใช้เป็น (W, A, S, D) โดยให้เดินไปทีละตาสลับกับซอมบี้ที่จะเดินมาหาเรา

จนเมื่อซอมบี้ใช้หลักการ BFS จนหาผู้เล่นเจอก็จะปรากฏดังนี้

สรุปบทความนี้

จากบทความนี้ เราได้ทำความรู้จักกับอัลกอริธึมการค้นหายอดนิยมทั้งสองแบบคือ Breadth-First Search (BFS) และ Depth-First Search (DFS) พร้อมตัวอย่างโค้ดภาษา Python ที่สามารถนำไปทดลองและประยุกต์ใช้ได้จริง ไม่ว่าจะเป็นการยกตัวอย่างของโหนดต่าง ๆ และการหาเส้นทางในแผนที่เกม แม้อัลกอริธึมเหล่านี้จะดูเรียบง่าย แต่ก็สามารถต่อยอดไปสู่การแก้ปัญหาที่ซับซ้อนมากขึ้นได้มากขึ้นในอนาคต เช่น เกมที่ใช้ AI ในการประมวลผลเส้นทาง, ระบบนำทาง, หรือแม้แต่การวิเคราะห์เครือข่ายสังคมออนไลน์ ลองนำความรู้ที่ได้ไปประยุกต์ใช้ดูนะครับ

ใครลองทำอะไรเจ๋ง ๆ มา แชร์กันได้เลยครับ 😄

Reference :
https://favtutor.com/blogs/breadth-first-search-python
https://favtutor.com/blogs/depth-first-search-python

DEV Community: Mint Z

[Boost]