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

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

Apr 6, 2025 - 15:52

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

ในยุคนี้ที่อะไร ๆ ก็ต้องเร็ว ต้องฉลาดและต้องหาให้เจอภายในพริบตา อัลกอริธึมการค้นหา (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')

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

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

ขั้นตอนที่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')

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

ผลลัพธ์ที่ได้จากการรันโค้ด 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)

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

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

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

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

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

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

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

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