Graph Theory คืออะไร?

Introduction

ในบทนี้เราก็จะมาศึกษากันต่อในเนื้อหาของ data structure แต่ว่าเป็น data structure ที่มีความซับซ้อนขึ้นมาจากบทที่แล้วนิดหน่อยนั้นก็คือ ‘Graph’ นั่นเอง

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

จากหลักฐานทางประวัติศาสตร์พบว่า ‘Graph Theory’ ได้มีการพูดถึงครั้งแรกเมื่อปี ค.ศ. 1735 โดยนักคณิตศาสตร์ที่ชื่อว่า Leonhard Euler โดย ณ ตอนนั้นเขาได้แก้ปัญหาที่ชื่อว่า “Seven Bridges of Königsberg” โดยปัญหาดังกล่าวก็มีความอยู่ว่า

ที่เมือง Königsberg จะมีสภาพเมืองที่เป็นเกาะที่มีแม่น้ำไหลผ่าน แต่ละเกาะถูกเชื่อมด้วยสะพานทั้งหมด 7 สะพาน (ดังรูป) โดยคำถามก็มีอยู่ว่า

“เริ่มจากตรงไหนก็ได้ เราจะสามารถเดินข้ามสะพานทั้งหมดได้หรือไม่ โดยที่ห้ามเดินข้ามสะพานที่เคยข้ามมาแล้ว”

เป็นคำถามที่น่าสนใจใช่ไหมครับ แนะนำว่าลองใช้เวลาสัก 2-3 นาทีลองหาวิธีแก้ปัญหานี้ดูครับ…

วิธีที่ง่ายที่สุดคือเริ่มจากการ brute force ลองหาทุกความเป็นไปได้ครับ ซึ่งถ้าเราลองหาเส้นทางจาก map ข้างบนแล้ว เราก็จะพบว่า “หาไม่เจอ” ครับ!?

แต่คำถามต่อไปก็คือ “ทำไมถึงเป็นไปไม่ได้หละ? อะไรคือเหตุผลเบื้องหลังที่บอกว่ามันเป็นไปไม่ได้?”

แน่นอนว่าการที่เรา brute force ลองทุกกรณีมันทำให้เรารู้คำตอบก็จริง แต่มันจะไม่ได้ทำให้เราได้เรียนรู้อะไรใหม่ ๆ เลย และก็ไม่ได้ทำให้เราเข้าใจคำตอบมากขึ้นด้วย ดังนั้นเรามาลองดูกันดีกว่าครับว่า Euler เขาเห็นอะไรในปัญหานี้ แล้วเขาสรุปวิธีแก้ปัญหาเอาไว้อย่างไรบ้าง

ทำความเข้าใจปัญหา

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

โดยเราจะเริ่มจากการใส่ label ให้เกาะก่อนหรือพื้นดินก่อน (ซึ่งในที่นี้ขอกำหนดให้เป็น A, B, C, D) จากนั้นเราจะสามารถมองเกาะเหล่านี้เป็นจุด ๆ หนึ่งที่มีสะพานเชื่อมผ่านได้; ในที่นี้ขอเรียกแต่ละเกาะว่า ‘Vertex’

และในส่วนของสะพานนั้นเราก็จะกำหนดให้เป็นเส้นเชื่อมหรือว่า edge ที่เชื่อมต่อระหว่าง vertex เป็นตัวแทนว่าเกาะไหนมีสะพานเชื่อมต่อหากันบ้าง

ซึ่งเมื่อเราลอง model ออกมาเราก็จะเห็นว่า จากแผนที่ที่ตอนแรกมี information ค่อนข้างเยอะ ก็จะถูกจำกัดเหลือแต่ข้อมูลที่จำเป็นเท่านั้นแล้ว ซึ่งมันทำให้เราเห็นปัญหาได้ชัดเจนมากขึ้น

ปัญหาของเราก็จะเปลี่ยนใหม่เป็น “เริ่มจาก vertex ไหนก็ได้ เราสามารถเดินผ่าน edge ครบทุก edge โดยที่ไม่เดินผ่าน edge ซ้ำได้หรือไม่”

เริ่มจากอะไรที่ง่าย ๆ ก่อน

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

ก่อนที่เราจะไปหาข้อสรุป “Seven Bridges of Königsberg” กันนั้น (ซึ่งมี 4 vertices, 7 bridges) เราควรจะเริ่มจากเคสที่ง่ายกว่านี้ก่อน จากนั้นค่อยหา observation เพื่อมาสรุปปัญหาที่ใหญ่ขึ้น

จะเห็นว่า graph ข้างต้น (graph แรก) จะประกอบไปด้วย 3 vertex และ 4 edges ซึ่งในเคสนี้แน่นอนว่าเราสามารถหา Eulerian Path ได้: A → X → B → X → A หรือ B → X → A → X → B

(ถึงตรงนี้ลองเพิ่ม edges ที่ละสองไปเรื่อย ๆ ดูครับ หรือลองเพิ่ม vertex แต่ให้แต่ละ vertex มี degree เป็นเลขคู่ แล้วสังเกตว่าเราจะหา Eulerian Path ได้ไหม)

จากตรงนี้เราจะสรุปได้ว่า ถ้าหากว่าทุก vertex มี degree เป็นเลขคู่ เราจะสามารถหา path ที่เป็น Eulerian Path ได้ เพราะเราสามารถเดินไปและเดินกลับผ่านทุก edge ได้นั่นเอง (และเราสามารถหาทางที่เดินกลับมาจุดเริ่มต้นได้เสมอ)

…

แล้วถ้าเราลองลบหรือเพิ่ม edge เข้าไปหนึ่งหละ? (จะมี 2 vertices ที่มี degree กลายเป็นคี่)

จากรูปข้างต้น (graph ที่หนึ่ง) ถ้าหากเราเริ่มที่จุด A เราจะไม่สามารถหา Eulerian Path ได้; ทางที่เราสามารถหา Eulerian Path ได้เราจะต้องเริ่มต้นที่ B (B → X → A → X) หรือไม่ก็เริ่มต้นที่ X (X → A → X → B) (ซึ่งจะเห็นได้ว่าจุดเริ่มต้นและจุดจบจะเป็นคนละ vertex)

เราสามารถสรุปออกมาได้ดังนี้ครับ

1. ถ้าทุก vertices มี degree เป็นเลขคู่ เราสามารถหา Eulerian Path ที่เดินออกจากจุด A เราก็จะกลับมาที่จุด A ได้
2. ถ้าหากว่าเรามีเพียง 2 vertices ที่มี degree เป็นคี่ เราจะสามารถหา Eulerian Path ได้โดยเริ่มที่จุดใดจุดหนึ่งในสองจุดนี้ และไปจบที่อีกจุดหนึ่งมี degree เป็นคี่เช่นกัน

(อธิบาย (2) เพิ่มเติม: ลองคิดภาพที่ทุก vertices มี degree เป็นคู่ เราจะหา Eulerian Path ที่สามารถเริ่มและจบที่จุดเดิมได้ใช่ไหมครับ ถ้าเราเพิ่ม edge ใหม่เข้าไปที่จุดนั้น การจะหา Eulerian Path ก็แค่ เริ่มเดินจากจุดนั้นและกลับมาจบที่จุดนั้นเหมือนเดิม จากนั้นใช้ edge ใหม่ที่พึ่งเพิ่มเข้ามาเดินไปหาอีก vertex แค่นี้เราก็จะเดินผ่านทุก edge แล้ว)

ข้อสรุป

จากปัญหา “Seven Bridges of Königsberg” ของเราจะพบว่าในทุก ๆ vertex มี degree เป็นเลขคี่ทั้งหมดเลย ดังนั้นเราจึงสรุปได้ว่า จากปัญหาข้างต้นเราไม่สามารถหา Eulerian Path ได้เลยนั่นเอง

(แต่ถ้าเราลองตัด edge ออก 1 อันจะพบว่า degree จะเปลี่ยนไป ทำให้เราสามารถหา Eulerian Path ได้ โดยที่เราจะเริ่มเดินจาก vertex ที่ degree เป็นคี่และไปจบ degree ที่เป็นคี่เหมือนกัน)

จะเห็นว่าจากปัญหาข้างต้นเราสามารถแก้ปัญหาได้โดยการนำปัญหามา model ใหม่ (เรียกว่า ‘Graph’) โดยตัดข้อมูลที่ไม่จำเป็นออก เพื่อให้เราเข้าใจปัญหามากขึ้น หลังจากนั้นเราก็สามารถที่จะเริ่มแก้ปัญหาจากเคสง่าย ๆ ไปสู่บทสรุปของเคสที่ใหญ่ขึ้นไปเรื่อย ๆ

และจากการทำความเข้าใจนี้เองมันไม่ได้ทำให้ Euler แค่สามารถแก้ปัญหา “Seven Bridges of Königsberg” ได้ แต่เขาสามารถที่จะแก้ปัญหา any kinds of bridges ได้หมดเลย

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

Graph รูปแบบต่าง ๆ

จากปัญหาข้างต้นจะเห็นแล้วว่า graph ประกอบไปด้วย components หลัก ๆ ก็คือ vertex และ edge โดยเราสามารถนำ components เหล่านี้ไปประกอบเป็น graph รูปแบบต่าง ๆ เพื่อ model ข้อมูลหรือปัญหาที่หลากหลายได้

หลัก ๆ แล้ว graph มีหลายประเภทมาก แต่ในหัวข้อนี้อยากจะขอยกตัวอย่างที่เจอบ่อย ๆ 3 ประเภท ได้แก่ directed graph, undirected graph และ weighted graph

Directed Graph คือ graph ที่ edge มีทิศทางและไม่สามารถเดินย้อนศรได้ ยกตัวอย่างเช่นถนนหรือเส้นทางของอะไรบางอย่างที่เดินได้ทางเดียว

Undirected Graph คือ graph ที่ edge ไม่มีทิศทาง อย่างเช่นปัญหาสะพานที่ได้ยกตัวอย่างกันไปที่เราสามารถเดินข้ามสะพานในทิศทางไหนก็ได้

Weighted Graph ก็เป็น graph ที่ edge มีน้ำหนักหรือค่าบางอย่างกำกับเอาไว้ อาจจะใช้แทน cost ของอะไรบางอย่างเช่นค่าผ่านทางหรือระยะทาง (weight ของเราจะเป็นบวกหรือลบก็ได้ขึ้นอยู่กับปัญหาว่า weight ของเรา represent อะไร)

Graph Implementation

ตอนนี้ทุกคนน่าจะเห็นภาพของ graph กันมาพอสมควรแล้ว เรามาดู implementation กันบ้างดีกว่า

สำหรับการ implement graph นั้นเราจะนิยมเขียนหลัก ๆ กัน 2 วิธีได้แก่ Adjacency Matrix และ Adjacency List

(ในการอธิบายขอใช้ \(V\) แทนจำนวน vertices และ \(E\) แทนจำนวน edges)

Adjacency Matrix

สำหรับการ implement แบบ Adjacency Matrix นั้นเราจะใช้ array 2 มิติในการ implement โดยที่กำหนดให้ G[u][v] เป็นตัวที่ represent ว่า vertex u มี edge เชื่อมไปหา vertex v หรือไม่ (โดยอาจจะเก็บค่าเป็น boolean ก็ได้หรือในกรณีที่ต้องการเก็บ weight เราก็อาจจะเก็บเป็นตัวเลข)

ส่วนสำหรับการ implement ใน Javascript ก็สามารถทำได้ง่าย ๆ ตามนี้เลย

1
const G = [];
2

3
// total vertices = 5
4
const V = 5;
5

6
// init default edge value (false) in graph
7
for (let i = 0; i < V; ++i) {
8
  for (let j = 0; j < V; ++j) {
9
    if (!G[i]) G[i] = [];
10
    G[i][j] = false;
11
  }
12
}
13

14
// add edges 0 -> 4, 3 -> 2, 1 -> 2, 2 -> 1
15
G[0][4] = true;
16
G[3][2] = true;
17
G[1][2] = true;
18
G[2][1] = true;
19

20
// remove edge 3 -> 2
21
G[3][2] = false;

จะเห็นว่าวิธีการนี้ทำให้เราสามารถ implement graph ได้ค่อนข้างง่ายเลย

• Look-up Edge Time: \(O(1)\)
• Insert/Delete Edge Time: \(O(1)\)
• Iterate over all Edges Time: \(O(V^2)\)
• Insert/Delete Vertex Time: \(O(V^2)\)
• Space complexity: \(O(V^2)\)

แต่ข้อเสียคือถ้าหากว่าเราต้องการจะ loop เพื่อเช็ค edges ทั้งหมดเราต้อง loop ไปใน matrix ขนาด \(n^2\) และการจะเพิ่ม vertex ก็ช้าเช่นกันเพราะต้องขยายทั้ง matrix (ถ้าเราใช้ fixed array มีความจำเป็นต้องสร้าง matrix ใหม่ขึ้นมา)

นอกจากนี้เราต้องเสีย space ในการเก็บข้อมูลค่อนข้างเยอะ เพราะว่าเราต้องเก็บ array 2 มิติที่มีขนาดเท่ากับจำนวนของ vertices กำลังสองนั้นเอง (Space Complexity: \(O(V^2)\))

Adjacency List

ส่วนสำหรับการ implement แบบ Adjacency List เราก็จะใช้ linked list หรือว่า array ในการเก็บว่าจาก vertex หนึ่งมี edge ไปที่ vertex ไหนได้อีกบ้าง

ส่วนสำหรับการ implement ใน Javascript ก็สามารถทำได้ง่าย ๆ ตามนี้เลยครับ

1
const G = {};
2

3
// total vertices = 5
4
const V = 5;
5

6
// init list in graph
7
for (let i = 0; i < V; ++i) {
8
  G[i] = [];
9
}
10

11
// add edges 0 -> 4, 3 -> 2, 1 -> 2, 2 -> 1
12
G[0].push(4);
13
G[3].push(2);
14
G[1].push(2);
15
G[2].push(1);
16

17
// remove edge 3 -> 2
18
let removeIndex = G[3].indexOf(2);
19
if (removeIndex > -1) {
20
    G[3].splice(removeIndex, 1);
21
}

สำหรับ time/space complexity ในแต่ละ operation เป็นไปตามนี้เลยครับ

• Look-up Edge Time: \(O(E)\)
• Insert Edge Time: \(O(1)\)
• Delete Edge Time: \(O(E)\)
• Iterate over all Edges Time: \(O(V + E)\)
• Insert Vertex Time: \(O(1)\)
• Delete Vertex Time: \(O(V + E)\)
• Space complexity: \(O(V + E)\)

จะเห็นว่าการ insert vertex สามารถทำได้ภายใน \(O(1)\) เพราะเราสามารถเพิ่ม vertex ใหม่เข้าไปใน G ได้เลย และนอกจากนี้ยังเก็บข้อมูลไม่กินพื้นที่เยอะเท่าแบบ matrix; แต่ในขณะเดียวกัน การลบและการดู edge ก็จะทำได้ช้าเพราะต้องไล่ไปใน list ของ vertex นั้น ๆ นั่นเอง

สุดท้ายนี้การจะเลือกใช้งานเราก็ต้องดูด้วยว่า context ของปัญหาเราเหมาะกับการเลือกใช้แบบไหน ขนาดของ vertices มีเยอะมากน้อยแค่ไหน หรือ operation อะไรที่เราต้องใช้เยอะเป็นพิเศษ

Traversal Algorithm

ก่อนจะจบบทนี้อยากจะขอฝากหนึ่งใน basic algorithm ที่สำคัญมาก ๆ สำหรับใช้งาน graph ก็คือ “Graph Travelsal Algorithm”

“กำหนดให้ graph มาหนึ่งกราฟ เราจะท่องไปในทุก ๆ vertices ได้อย่างไร?”

สำหรับการ Traverse Graph Algorithm นั้นสามารถแบ่งเป็นวิธีการหลัก ๆ ได้ 2 วิธีนั้นก็คือ Depth-first search (DFS) และ Breadth-first search (BFS) เดี๋ยวเรามาดูกันดีกว่าว่าแต่ละตัวมีความเหมือนหรือแตกต่างยังไงกันบ้าง

Depth-first search (DFS)

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

ซึ่งจะเห็นว่าเราจะต้อง traverse ไปในแต่ละ edge และ vertex ดังนั้น time complexity ของ algorithm นี้จึงเป็น \(O(V + E)\)

1
class Stack {
19 collapsed lines
2
  constructor() {
3
    this.list = [];
4
    this.top = -1;
5
  }
6
  push(value) {
7
    ++this.top;
8
    this.list[this.top] = value;
9
  }
10
  pop() {
11
    if (this.top === -1) {
12
      return null;
13
    }
14
    const top = this.list[this.top];
15
    --this.top;
16
    return top;
17
  }
18
  isEmpty() {
19
    return this.top === -1;
20
  }
21
}
22

23
function dfs(G, start) {
24
  // check if vertex visited
25
  const visited = [];
26
  const stack = new Stack();
27
  // push start node to stack
28
  stack.push(start);
29

30
  while (!stack.isEmpty()) {
31
    // pop and print
32
    const v = stack.pop();
33

34
    if (!visited[v]) {
35
      console.log("visit", v);
36
      visited[v] = true;
37
    }
38

39
    // go to all adjacency vertices
40
    for (let i = 0; i < G[v].length; ++i) {
41
      if (!visited[G[v][i]]) stack.push(G[v][i]);
42
    }
43
  }
44
}
45

46
// Total Vertices = 6
47
// Edges: 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 3, 2-> 4, 4 -> 5
48
const G = {};
49
const V = 6;
50
for (let i = 0; i < V; ++i) {
51
  G[i] = [];
52
}
53
G[0].push(1);
54
G[0].push(2);
55
G[1].push(2);
56
G[2].push(3);
57
G[2].push(4);
58
G[4].push(5);
59

60
// DFS Traversal
61
dfs(G, 0);

Breadth-first search (BFS)

สำหรับการ traverse graph แบบ BFS นั้นเราจะค่อย ๆ ไล่ traverse ไปทีละ level เป็นชั้น ๆ ไปโดยสำหรับการ implement algorithm นี้จะนิยมใช้เป็น Queue ต่างกับ DFS ที่นิยมใช้ Stack

ซึ่งจะเห็นว่าเราจะต้อง traverse ไปในแต่ละ edge และ vertex ดังนั้น time complexity ของ algorithm นี้จึงเป็น \(O(V + E)\) เช่นเดียวกับ DFS

1
class Queue {
23 collapsed lines
2
  constructor() {
3
    this.queue = [];
4
    this.head = -1;
5
    this.tail = -1;
6
  }
7
  enqueue(value) {
8
    if (this.head === -1) {
9
      this.head = 0;
10
    }
11
    ++this.tail;
12
    this.queue[this.tail] = value;
13
  }
14
  dequeue() {
15
    if (this.head === -1 || this.head > this.tail) {
16
      return null;
17
    }
18
    const head = this.queue[this.head];
19
    this.head++;
20
    return head;
21
  }
22
  isEmpty() {
23
    return this.head === -1 || this.head > this.tail;
24
  }
25
}
26

27
function bfs(G, start) {
28
  // check if vertex visited
29
  const visited = [];
30
  const queue = new Queue();
31
  // push start node to queue
32
  queue.enqueue(start);
33

34
  while (!queue.isEmpty()) {
35
    // dequeue and print
36
    const v = queue.dequeue();
37

38
    if (!visited[v]) {
39
      console.log("visit", v);
40
      visited[v] = true;
41
    }
42
    // go to all adjacency vertices
43
    for (let i = 0; i < G[v].length; ++i) {
44
      if (!visited[G[v][i]]) queue.enqueue(G[v][i]);
45
    }
46
  }
47
}
48

49
// Total Vertices = 6
50
// Edges: 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 3, 2-> 4, 4 -> 5
51
const G = {};
52
const V = 6;
53
for (let i = 0; i < V; ++i) {
54
  G[i] = [];
55
}
56
G[0].push(1);
57
G[0].push(2);
58
G[1].push(2);
59
G[2].push(3);
60
G[2].push(4);
61
G[4].push(5);
62

63
// BFS Traversal
64
bfs(G, 0);

บทสรุป

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

นอกจาก traversal algorithm แล้ว ใน topic ของ graph theory ยังมีปัญหาและ algorithm อีกเยอะมากที่น่าสนใจเช่น

• Fleury’s Algorithm สำหรับใช้หา Eulerian Path
• Shortest Path Algorithm ที่ใช้หา shortest path ระหว่าง 2 vertex (หรือหลาย ๆ vertex พร้อมกัน) เช่น Dijkstra Algorithm, A* Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm
• Cycle Detection Algorithm ต่าง ๆ อย่างเช่น Floyd’s Cycle-Finding Algorithm
• รวมไปถึงปัญหาอื่น ๆ ที่น่าสนใจอย่างเช่น Hamiltonian Cycle หรือ Four Color Theorem ไว้ถ้ามีโอกาสจะมาเจาะลึกแต่ละเรื่องกันอีกที สำหรับในบทนี้หวังว่าทุกคนจะสนุกไปกับการศึกษาเรื่อง graph และ application ต่าง ๆ ของมันนะครับ

Challenge Problem

Coming Soon…