Graphs & DFS — พื้นฐาน & แนวคิด

หมวดนี้เราจะรู้จัก graph (กราฟ) ซึ่งเป็น data structure (โครงสร้างข้อมูล) ที่ยืดหยุ่นที่สุดอันหนึ่ง ถ้าคุณยังไม่เคยเรียน graph มาก่อนไม่ต้องกังวล เราจะเริ่มจากศูนย์ ค่อย ๆ ปูตั้งแต่ graph คืออะไร เก็บมันในโค้ดยังไง แล้วจึงเรียนเทคนิค traverse (เดินไล่) graph ตัวแรกคือ DFS (Depth-First Search) หรือการลุยลึก

กราฟคืออะไร

graph คือชุดของ node (โหนด หรือเรียก vertex) ที่มี edge (เส้นเชื่อม) โยงระหว่างกัน ลองนึกถึงแผนที่เมือง เมืองแต่ละเมืองคือ node ถนนที่เชื่อมสองเมืองคือ edge หรือนึกถึงเพื่อนใน social network คนคือ node ความเป็นเพื่อนคือ edge อะไรก็ตามที่เป็นความสัมพันธ์ ระหว่างของหลาย ๆ ชิ้น เอามาเป็น graph ได้หมด

tree (ต้นไม้) ที่เราเรียนไปก่อนหน้านี้จริง ๆ ก็เป็น graph ชนิดพิเศษ (graph ที่ไม่มีวงและเชื่อมกันหมด) graph ทั่วไปอิสระกว่านั้น มันมี cycle (วง) ได้ มีหลายกลุ่มที่ไม่เชื่อมกันได้ และ node หนึ่งจะมี edge กี่เส้นก็ได้

# กราฟไม่มีทิศ วาดเป็นภาพ
        #     0 --- 1
        #     |     |
        #     2 --- 3
        #           |
        #           4
        #
        # node = {0,1,2,3,4} ห้าจุด
        # edge = เส้นเชื่อม เช่น 0-1, 0-2, 1-3, 2-3, 3-4

มีทิศ vs ไม่มีทิศ (directed vs undirected)

graph แบบ undirected (ไม่มีทิศ) edge เดินได้สองทาง เช่นถ้า A เป็นเพื่อนกับ B แล้ว B ก็เป็นเพื่อนกับ A ด้วย ส่วน graph แบบ directed (มีทิศ) edge เดินได้ทางเดียวตามหัวลูกศร เช่นถนนวันเวย์ ไปจาก A ถึง B ได้ แต่ย้อนกลับไม่ได้ หรือการติดตามบน social ที่ A ติดตาม B ไม่ได้แปลว่า B ติดตาม A การรู้ว่าโจทย์เป็น graph แบบไหนสำคัญมาก เพราะมันเปลี่ยนวิธีเก็บและวิธีเดิน

เก็บกราฟยังไง — adjacency list

วิธีเก็บ graph ที่นิยมและใช้ง่ายสุดคือ adjacency list (ลิสต์เพื่อนบ้าน) ไอเดียคือใช้ dict ที่ key เป็น node และ value เป็น list ของ node ที่มันเชื่อมถึงโดยตรง พูดง่าย ๆ คือ สำหรับแต่ละ node เราจดไว้ว่ามันเดินไปหาใครได้บ้าง

# สร้าง adjacency list จากภาพด้านบน
from collections import defaultdict

edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)   # ไม่มีทิศ ต้องใส่ทั้งสองทาง

# graph[0] = [1, 2]  -> node 0 เชื่อมกับ 1 และ 2
# graph[3] = [1, 2, 4]

# ถ้าเป็นกราฟมีทิศ (a -> b เท่านั้น) ใส่ทางเดียว
# graph[a].append(b)   # ไม่ต้องใส่ graph[b].append(a)

DFS — ลุยลึก

DFS (Depth-First Search) คือวิธี traverse graph แบบ ลุยลึกไปทางหนึ่งให้สุดก่อน แล้วค่อยถอยกลับมาลองทางอื่น เหมือนเดินในเขาวงกตแล้วยึดกำแพงขวาไว้ตลอด เดินลึกเข้าไปเรื่อย ๆ จนตัน ค่อยถอยกลับ วิธีที่เขียนง่ายที่สุดคือใช้ recursion (การเรียกตัวเอง)

สิ่งที่ขาดไม่ได้เลยในการเดิน graph คือ set visited (เคยเยือน) ที่จำว่าเราเคยไป node ไหนมาแล้วบ้าง เพราะ graph มี cycle ได้ ถ้าไม่จำ เราจะเดินวนกลับมาที่เดิมไม่รู้จบ (infinite loop) กฎคือ ก่อนจะเดินเข้า node ไหน เช็คก่อนว่าเคยไปหรือยัง ถ้ายังค่อยไป และทันทีที่ไปถึงให้ mark เป็น visited

# template DFS ด้วย recursion จำโครงนี้ไว้ใช้ได้ทุกข้อ
def dfs(node, graph, visited):
    visited.add(node)              # ทำเครื่องหมายว่ามาถึงแล้ว
    # ... ทำอะไรกับ node ตรงนี้ เช่น นับ, เก็บค่า ...
    for nxt in graph[node]:        # ลองเพื่อนบ้านทีละตัว
        if nxt not in visited:     # ถ้ายังไม่เคยไป
            dfs(nxt, graph, visited)   # ลุยลึกต่อ

visited = set()
dfs(0, graph, visited)             # เริ่มจาก node 0