Graph
กราฟ G = (V, E) ประกอบด้วยเซตของ vertex (V) และเซตของ edge (E) โดยแต่ละ edge คือคู่ (v, w) ที่บอกความสัมพันธ์ระหว่าง vertex
นิยามกราฟ
ตัวอย่าง
V = { A, B, C, D }
E = { (A,B), (A,D), (B,C), (B,D) }
สิ่งที่เป็น vertex และ edge ได้ในชีวิตจริง:
- หน้าเว็บกับลิงก์
- เพื่อนใน Facebook
- เมธอดที่เรียกหากันในโปรแกรม
- แผนที่ถนน / เส้นทางบิน
- ผังตระกูล / วิชาบังคับก่อน (pre-requisite)
ปัญหาคลาสสิกที่ให้กำเนิดทฤษฎีกราฟคือ สะพานเมือง Königsberg
ชนิดของกราฟ
| ชนิด | ลักษณะ |
|---|---|
| Undirected graph | edge ไม่มีทิศทาง — (v,w) เท่ากับ (w,v) |
| Directed graph (digraph) | edge มีทิศทาง — ลำดับใน edge สำคัญ |
| Weighted graph | edge มีค่าที่สาม คือ weight หรือ cost |
| Directed weighted graph | มีทั้งทิศทางและน้ำหนัก |
กราฟจากชีวิตจริง
V = คน 6 คน: John, Mary, Joe, Helen, Tom, Paul (อายุ 12, 15, 12, 15, 13, 13)
E = { (x,y) | x อายุน้อยกว่า y } → เป็น directed graph
คำศัพท์: path, cycle, adjacent
| คำ | ความหมาย |
|---|---|
| Adjacent | vertex 2 ตัวที่มี edge เชื่อมกันโดยตรง |
| Path | ลำดับของ vertex w1, w2, …, wn ที่เชื่อมต่อกัน |
| ความยาวของ path | จำนวน edge บนเส้นทาง = n - 1 |
| Loop | edge (v, v) ที่วิ่งจาก vertex กลับมาที่ตัวเอง |
| Cycle | path ที่เริ่มและจบที่ vertex เดียวกัน (v0 = vn) |
| Simple path | path ที่ไม่ซ้ำ vertex (ยกเว้นตัวแรกอาจเป็นตัวสุดท้าย) |
| Simple cycle | เป็นทั้ง cycle และ simple path |
ตัวอย่างเส้นทาง
Austin → Dallas → Denver ความยาว = 2 Austin → Houston → Atlanta → Washington → Dallas → Denver ความยาว = 5
Complete graph และจำนวน edge
Complete graph = ทุก vertex เชื่อมตรงถึงทุก vertex ที่เหลือ
| ชนิด | จำนวน edge เมื่อมี N vertex |
|---|---|
| Directed | N × (N-1) |
| Undirected | N × (N-1) / 2 |
พิสูจน์ฝั่ง undirected
N=2 → E = 1 N=3 → E = 1+2 = 3 N=4 → E = 1+2+3 = 6 N=5 → E = 1+2+3+4 = 10 E = 1 + 2 + … + (N-1) = ((N+1)·N/2) - N = (N² + N - 2N)/2 = N(N-1)/2
Connectivity
| ชนิดกราฟ | คำ | เงื่อนไข |
|---|---|---|
| Undirected | Connected | ทุกคู่ u≠v มี path ถึงกัน |
| Complete / fully connected | ทุกคู่ u≠v มี edge ตรงถึงกัน | |
| Directed | Strongly connected | มี path จากทุก vertex ไปทุก vertex ตามทิศทาง |
| Weakly connected | มี path ถึงกันเมื่อไม่สนทิศทางของ edge |
ต้นไม้เป็นกราฟไหม
ใช่ — tree คือกราฟที่:
- undirected
- acyclic (ไม่มี cycle)
- connected (เชื่อมถึงกันหมด)
- มี edge เท่ากับ V - 1 เสมอ
ต้นไม้ทุกต้นเป็นกราฟ แต่กราฟไม่จำเป็นต้องเป็นต้นไม้
Adjacency Matrix
ใช้ array 2 มิติขนาด n × n โดย vertex ถูก index เป็น 0, 1, …, n-1
A[i][j] = 1 ถ้ามี edge จาก i ไป j A[i][j] = 0 ถ้าไม่มี
กราฟนี้ตรงกับ adjacency matrix และ adjacency list ด้านล่าง
ตัวอย่างกราฟ 5 vertex
| i \ j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 | 1 |
| 3 | 1 | 1 | 1 | 0 | 0 |
| 4 | 0 | 1 | 1 | 0 | 0 |
กราฟถ่วงน้ำหนักใช้เก็บ weight ในช่องแทนเลข 1 เช่น A[0][1] = 5 และใส่ 0 เมื่อไม่มี edge
Adjacency List
ใช้ array 1 มิติของ linked list โดย L[i] เก็บ vertex ทุกตัวที่ติดกับ vertex i (ไม่เรียงลำดับ)
0 → {1, 3}
1 → {0, 2, 3, 4}
2 → {1, 3, 4}
3 → {0, 1, 2}
4 → {1, 2}
แบบถ่วงน้ำหนักเก็บเป็นคู่ (ปลายทาง, weight):
0 → { (1,5), (3,21) }
1 → { (2,5), (4,20) }
2 → { (3,13), (4,-8) }
3 → { (1,9) }
4 → { }
เทียบ 2 วิธีเก็บ
| คำถาม | Adjacency Matrix | Adjacency List |
|---|---|---|
| u กับ v ติดกันไหม | Θ(1) — อ่าน A[u][v] ตรง ๆ | O(V) — ต้องไล่ list |
| vertex ไหนติดกับ v บ้าง | O(V) — ไล่ทั้งแถว | Θ(V) แต่จริง ๆ เท่ากับจำนวนเพื่อนบ้าน |
| หน่วยความจำ | V² เสมอ | ประหยัดกว่า — เท่ากับจำนวน vertex + edge |
| เหมาะกับ | กราฟหนาแน่น (dense) | กราฟเบาบาง (sparse) |
DFS บนกราฟ
- เดินให้ลึกที่สุดเท่าที่จะไปได้
- ถอยหลังให้น้อยที่สุดเมื่อเจอทางตัน (vertex ถูก mark แล้ว หรือไม่มีทางต่อ)
- ใช้ stack
1. push vertex ที่ติดกันลง stack 2. ทำซ้ำข้อ 1 จนเจอทางตัน 3. pop แล้วดูว่าตัวบนสุดยังมีเพื่อนบ้านที่ยังไม่ไปหรือไม่ - ถ้ามี → กลับไปข้อ 1 - ถ้าไม่มี → ทำข้อ 3 ซ้ำ
DFS บนกราฟใกล้เคียงกับ preorder traversal ของต้นไม้ ต่างตรงที่ต้อง mark ว่า vertex ไหนเคยไปแล้ว เพราะกราฟมี cycle ได้
BFS บนกราฟ
- ไล่ vertex ชั้น i ให้ครบก่อนไปชั้น i+1
- ใช้ queue
1. enqueue เพื่อนบ้านทั้งหมดของ vertex ปัจจุบัน (เฉพาะตัวที่ยังไม่เคยไปและยังไม่อยู่ใน queue) 2. dequeue แล้วใช้ตัวนั้นทำข้อ 1 ซ้ำ
แบบฝึกจากสไลด์
DFS: 0, 1, 2, 3, 4, 6, 5 หรือ 0, 1, 3, 2, 4, 6, 5 BFS: 0, 1, 3, 2, 5, 6, 4
Minimum Spanning Tree (MST)
หาต้นไม้ที่เชื่อมทุก vertex โดยผลรวม weight น้อยที่สุด มี 2 อัลกอริทึม ทั้งคู่เป็น greedy algorithm
| อัลกอริทึม | แนวคิด |
|---|---|
| Prim's | เริ่มจาก vertex เดียว แล้วขยาย — เลือก edge ที่เบาสุดที่ต่อจากกลุ่มที่มีอยู่ออกไปหา vertex ใหม่ |
| Kruskal's | เรียง edge ทั้งกราฟจากเบาไปหนัก แล้วหยิบทีละเส้น ข้ามเส้นที่ทำให้เกิด cycle |
Prim's algorithm
กราฟ 7 vertex → MST มี 6 เส้นเสมอ (V - 1)
ตัวอย่างจากสไลด์ (7 vertex: A–G)
weight ที่ถูกเลือกเข้ามาใน MST: 2 + 3 + 4 + 4 + 11 + 16 → ระยะทางรวมน้อยที่สุด
สังเกต: MST ของกราฟ n vertex มี edge เท่ากับ n - 1 เส้นเสมอ (6 เส้นสำหรับ 7 vertex)
Kruskal's algorithm
1. เรียง edge ทั้งหมดจาก weight น้อยไปมาก 2. หยิบ edge ที่เบาที่สุดที่ยังไม่ได้ใช้ 3. ถ้าใส่แล้วเกิด cycle → ข้าม ถ้าไม่เกิด cycle → ใส่เข้า MST 4. ทำจนได้ edge ครบ n-1 เส้น
ผลลัพธ์ MST ของ Prim กับ Kruskal มีน้ำหนักรวมเท่ากันเสมอ (แม้เส้นที่เลือกอาจต่างกันเมื่อมี weight ซ้ำ)
Dijkstra — shortest path from source
ระวังสับสน: shortest path tree ไม่ใช่ minimum spanning tree —
MST สนใจผลรวม weight ทั้งต้น ส่วน Dijkstra สนใจระยะทางจาก source ไปแต่ละ vertex
ตัวแปรที่ใช้ต่อ vertex:
d(v)= ระยะทางสะสมจาก source มาถึง v ที่ดีที่สุดตอนนี้p(v)= vertex ก่อนหน้า (parent) บนเส้นทางที่ดีที่สุด
เริ่มต้น: d(s) = 0, p(s) = null
d(v) = ∞ สำหรับ vertex อื่น
เงื่อนไขการอัปเดต (relaxation):
ถ้า d(u) + w(u,v) < d(v)
แล้ว d(v) = d(u) + w(u,v), p(v) = u
ตัวอย่าง
d(u) = 4 และ edge u→v หนัก 2 ส่วน d(v) ปัจจุบัน = 7 4 + 2 = 6 < 7 → อัปเดต d(v) = 6, p(v) = u
เส้นทางจาก S: d = 0, 7, 4, 7, 18, 19, 20 … เส้นทาง 4 + 3 + 2 = 9 ดีกว่าเส้นตรงที่หนัก 18 จึงอัปเดต