Giao diện
Part 7: Graph Algorithms Advanced
Graph là cấu trúc dữ liệu mạnh mẽ nhất để mô hình hóa mối quan hệ giữa các thực thể.
Tại sao Graph?
Rất nhiều bài toán thực tế có thể được mô hình hóa bằng đồ thị:
┌─────────────────────────────────────────────────────────────────┐
│ GRAPHS IN REAL WORLD │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 🌐 SOCIAL NETWORKS 🗺️ MAPS & NAVIGATION │
│ ───────────────── ────────────────── │
│ Users = Nodes Cities = Nodes │
│ Friendships = Edges Roads = Edges │
│ │
│ 📦 DEPENDENCY MANAGEMENT 🔌 COMPUTER NETWORKS │
│ ───────────────────────── ──────────────────── │
│ Packages = Nodes Devices = Nodes │
│ Dependencies = Edges Connections = Edges │
│ │
│ 🧬 MOLECULAR STRUCTURES 🎮 GAME AI (Pathfinding) │
│ ─────────────────────── ───────────────────── │
│ Atoms = Nodes Positions = Nodes │
│ Bonds = Edges Moves = Edges │
│ │
└─────────────────────────────────────────────────────────────────┘Graph là gì?
Định nghĩa
Graph G = (V, E) gồm:
- V (Vertices/Nodes): Tập các đỉnh
- E (Edges): Tập các cạnh nối 2 đỉnh
Undirected Graph Directed Graph (Digraph)
───────────────── ────────────────────────
0 ─── 1 0 ───► 1
│ │ │ │
│ │ ▼ ▼
3 ─── 2 3 ◄─── 2
Edge (0,1) = Edge (1,0) Edge (0,1) ≠ Edge (1,0)Phân loại
| Loại | Mô tả | Ví dụ |
|---|---|---|
| Undirected | Cạnh 2 chiều | Bạn bè trên Facebook |
| Directed | Cạnh 1 chiều | Follow trên Twitter |
| Weighted | Cạnh có trọng số | Bản đồ với khoảng cách |
| Unweighted | Cạnh không có trọng số | Mạng xã hội đơn giản |
| Cyclic | Có chu trình | Đường đi vòng tròn |
| Acyclic | Không có chu trình | DAG - Dependency graph |
Analogy: Mạng xã hội
┌─────────────────────────────────────────────────────────────────┐
│ SOCIAL NETWORK GRAPH │
├─────────────────────────────────────────────────────────────────┤
│ │
│ FACEBOOK (Undirected) TWITTER (Directed) │
│ ───────────────────── ────────────────── │
│ │
│ 👤 Alice 👤 Alice │
│ / | \ ↗ ↘ │
│ / | \ / \ │
│ 👤Bob 👤Carol 👤Dan 👤Bob 👤Carol │
│ \ | ↖ ↗ │
│ \ | \ / │
│ 👤Eve 👤Dan │
│ │
│ Nếu Alice kết bạn Bob, Alice follow Bob, │
│ thì Bob cũng kết bạn Alice nhưng Bob không follow Alice│
│ │
└─────────────────────────────────────────────────────────────────┘Thuật ngữ quan trọng
| Thuật ngữ | Định nghĩa |
|---|---|
| Vertex/Node | Đỉnh của đồ thị |
| Edge | Cạnh nối 2 đỉnh |
| Adjacent | 2 đỉnh kề nhau (có cạnh nối) |
| Degree | Số cạnh nối với 1 đỉnh |
| Path | Dãy các đỉnh liên tiếp nối với nhau |
| Cycle | Path bắt đầu và kết thúc tại cùng 1 đỉnh |
| Connected | Có đường đi từ mọi đỉnh đến mọi đỉnh khác |
| Component | Nhóm các đỉnh connected với nhau |
Module Structure
📘 Part 1: Representation & Traversal
| Topic | Description |
|---|---|
| Biểu diễn đồ thị | Adjacency Matrix vs List |
| BFS | Breadth-First Search |
| DFS | Depth-First Search |
📙 Part 2: Shortest Paths
| Topic | Description |
|---|---|
| Dijkstra | priority_queue, non-negative weights |
| Bellman-Ford | Negative weights, cycle detection |
📕 Part 3: Advanced (Coming Soon)
- Minimum Spanning Tree (Prim, Kruskal)
- Topological Sort
- Floyd-Warshall
Prerequisites
📋 YÊU CẦU
- ✅ STL Containers — vector, queue, stack
- ✅ Functions — Recursion
- 🔸 Big O notation (recommended)
Learning Path
"The shortest path between two nodes is not always the most important path." — Graph Theory Wisdom