คุณแสดงกราฟอย่างไร: รายชื่อติดกัน หรือเมทริกซ์ติดกัน?

Question

IT Interview Practice · Accepted Answer

**กราฟ** คือชุดของ **จุดยอด** ที่เชื่อมต่อด้วย **ขอบ** สองการแสดงแบบมาตรฐานคือ **รายชื่อติดกัน** (จุดยอดแต่ละจุดเก็บเพื่อนบ้านของมัน) และ **เมทริกซ์ติดกัน** (กริด V×V ของค่าบูลีน) การเลือกขึ้นอยู่กับ **ความหนาแน่น** ของกราฟ

## สองรูปแบบ

```text
Graph:  0 - 1
        |   |
        2 - 3

Adjacency list:          Adjacency matrix:
0: [1, 2]                    0 1 2 3
1: [0, 3]                 0 [0 1 1 0]
2: [0, 3]                 1 [1 0 0 1]
3: [1, 2]                 2 [1 0 0 1]
                          3 [0 1 1 0]
```

## โค้ด

```python
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1]            # O(1) to get a vertex's neighbors

# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1  # O(1) edge lookup
```

## การเปรียบเทียบ (จุดยอด V ขอบ E)

| | รายชื่อติดกัน | เมทริกซ์ติดกัน |
|---|---|---|
| พื้นที่ | O(V + E) | O(V²) |
| ขอบมีอยู่หรือไม่ | O(degree) | O(1) |
| วนซ้ำเพื่อนบ้าน | O(degree) | O(V) |
| ดีที่สุดสำหรับ | กราฟแบบเบาบาง | กราฟแบบหนาแน่น |

## ทำไมจึงสำคัญ

กราฟในโลกแห่งความจริงส่วนใหญ่ (เครือข่ายสังคม แผนที่ถนน กราฟการพึ่งพา) มี **ความเบาบาง** ดังนั้นรายชื่อที่อยู่ติดกันจึงประหยัดพื้นที่มหาศาล และเร่งความเร็วของการข้ามผ่านเช่น BFS/DFS

การรู้การแลกเปลี่ยนนี้ช่วยให้คุณเลือกการแสดงที่ทำให้อัลกอริทึมกราฟของคุณมีประสิทธิภาพ แทนที่จะใช้หน่วยความจำ O(V²) โดยไม่ตั้งใจ

	รายชื่อติดกัน	เมทริกซ์ติดกัน
พื้นที่	O(V + E)	O(V²)
ขอบมีอยู่หรือไม่	O(degree)	O(1)
วนซ้ำเพื่อนบ้าน	O(degree)	O(V)
ดีที่สุดสำหรับ	กราฟแบบเบาบาง	กราฟแบบหนาแน่น

สองรูปแบบ

โค้ด

การเปรียบเทียบ (จุดยอด V ขอบ E)

ทำไมจึงสำคัญ

คำถามที่เกี่ยวข้อง