On this page
บทเรียน: Graph
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
node เชื่อมกันด้วย edge — BFS, DFS และการระวัง visited เพื่อกันวนซ้ำ
Graph คือ node (จุด) ที่เชื่อมกันด้วย edge (เส้น) ใช้แทนสิ่งที่มีความสัมพันธ์ เช่นเพื่อนใน social network, แผนที่ถนน นิยมเก็บเป็น adjacency list (dict ของ list)
BFS บน graph
BFS กวาดทีละชั้นจากจุดเริ่ม เหมาะกับการหาเส้นทางสั้นสุดเมื่อ edge มีน้ำหนักเท่ากัน ต้องมี visited set กันวนซ้ำเสมอ
python
from collections import deque
def bfs(graph, start):
visited = {start}
q = deque([start])
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
q.append(nb)
return order
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(bfs(graph, 1)) # [1, 2, 3, 4]DFS แบบ recursion
python
def dfs(graph, node, visited):
if node in visited:
return
visited.add(node)
print(node)
for nb in graph[node]:
dfs(graph, nb, visited)ข้อควรระวัง
ลืม visited set = วนไม่จบในกราฟที่มี cycle โจทย์ยอดฮิต: number of islands, course schedule (topological sort), clone graph