Giao diện
📊 Biểu diễn đồ thị — Matrix vs List
Hai cách phổ biến nhất để lưu trữ đồ thị trong máy tính: Adjacency Matrix và Adjacency List.
Graph mẫu
Trong suốt bài học, chúng ta sẽ dùng đồ thị này làm ví dụ:
SAMPLE GRAPH (Undirected, Unweighted)
─────────────────────────────────────
0 ───── 1
│ \ │
│ \ │
│ \ │
3 ───── 2
Vertices: {0, 1, 2, 3}
Edges: {(0,1), (0,2), (0,3), (1,2), (2,3)}1. Adjacency Matrix
Concept
Adjacency Matrix là ma trận 2D kích thước V × V, trong đó matrix[i][j] = 1 nếu có cạnh từ đỉnh i đến đỉnh j.
ADJACENCY MATRIX
─────────────────
0 1 2 3
┌───┬───┬───┬───┐
0 │ 0 │ 1 │ 1 │ 1 │ ← Node 0 nối với 1, 2, 3
├───┼───┼───┼───┤
1 │ 1 │ 0 │ 1 │ 0 │ ← Node 1 nối với 0, 2
├───┼───┼───┼───┤
2 │ 1 │ 1 │ 0 │ 1 │ ← Node 2 nối với 0, 1, 3
├───┼───┼───┼───┤
3 │ 1 │ 0 │ 1 │ 0 │ ← Node 3 nối với 0, 2
└───┴───┴───┴───┘
matrix[0][1] = 1 → Có cạnh từ 0 đến 1
matrix[1][3] = 0 → Không có cạnh từ 1 đến 3Implementation
cpp
#include <iostream>
#include <vector>
class GraphMatrix {
int V; // Number of vertices
std::vector<std::vector<int>> matrix;
public:
explicit GraphMatrix(int vertices) : V(vertices) {
// Initialize V x V matrix with all 0s
matrix.resize(V, std::vector<int>(V, 0));
}
// Add edge (undirected)
void addEdge(int u, int v) {
matrix[u][v] = 1;
matrix[v][u] = 1; // Bỏ dòng này nếu directed graph
}
// Check if edge exists
bool hasEdge(int u, int v) const {
return matrix[u][v] == 1;
}
// Get all neighbors of vertex v
std::vector<int> getNeighbors(int v) const {
std::vector<int> neighbors;
for (int i = 0; i < V; ++i) {
if (matrix[v][i] == 1) {
neighbors.push_back(i);
}
}
return neighbors;
}
// Print matrix
void print() const {
std::cout << "Adjacency Matrix:\n";
std::cout << " ";
for (int i = 0; i < V; ++i) {
std::cout << i << " ";
}
std::cout << "\n";
for (int i = 0; i < V; ++i) {
std::cout << i << " [ ";
for (int j = 0; j < V; ++j) {
std::cout << matrix[i][j] << " ";
}
std::cout << "]\n";
}
}
};
int main() {
GraphMatrix g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.print();
std::cout << "\nEdge (0,1) exists? " << (g.hasEdge(0, 1) ? "Yes" : "No") << "\n";
std::cout << "Edge (1,3) exists? " << (g.hasEdge(1, 3) ? "Yes" : "No") << "\n";
std::cout << "\nNeighbors of 2: ";
for (int n : g.getNeighbors(2)) {
std::cout << n << " ";
}
std::cout << "\n";
return 0;
}Output:
Adjacency Matrix:
0 1 2 3
0 [ 0 1 1 1 ]
1 [ 1 0 1 0 ]
2 [ 1 1 0 1 ]
3 [ 1 0 1 0 ]
Edge (0,1) exists? Yes
Edge (1,3) exists? No
Neighbors of 2: 0 1 32. Adjacency List
Concept
Adjacency List lưu một danh sách các đỉnh kề cho mỗi đỉnh.
ADJACENCY LIST
───────────────
0 → [1, 2, 3] Node 0 nối với 1, 2, 3
1 → [0, 2] Node 1 nối với 0, 2
2 → [0, 1, 3] Node 2 nối với 0, 1, 3
3 → [0, 2] Node 3 nối với 0, 2
Visualization:
0 ──┬──► 1
├──► 2
└──► 3
1 ──┬──► 0
└──► 2
2 ──┬──► 0
├──► 1
└──► 3
3 ──┬──► 0
└──► 2Implementation
cpp
#include <iostream>
#include <vector>
class GraphList {
int V; // Number of vertices
std::vector<std::vector<int>> adjList;
public:
explicit GraphList(int vertices) : V(vertices) {
adjList.resize(V);
}
// Add edge (undirected)
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // Bỏ dòng này nếu directed graph
}
// Check if edge exists - O(degree)
bool hasEdge(int u, int v) const {
for (int neighbor : adjList[u]) {
if (neighbor == v) return true;
}
return false;
}
// Get all neighbors - O(1)
const std::vector<int>& getNeighbors(int v) const {
return adjList[v];
}
// Get number of vertices
int getV() const { return V; }
// Print adjacency list
void print() const {
std::cout << "Adjacency List:\n";
for (int i = 0; i < V; ++i) {
std::cout << i << " → [";
for (size_t j = 0; j < adjList[i].size(); ++j) {
std::cout << adjList[i][j];
if (j < adjList[i].size() - 1) std::cout << ", ";
}
std::cout << "]\n";
}
}
};
int main() {
GraphList g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.print();
std::cout << "\nEdge (0,1) exists? " << (g.hasEdge(0, 1) ? "Yes" : "No") << "\n";
std::cout << "Edge (1,3) exists? " << (g.hasEdge(1, 3) ? "Yes" : "No") << "\n";
std::cout << "\nNeighbors of 2: ";
for (int n : g.getNeighbors(2)) {
std::cout << n << " ";
}
std::cout << "\n";
return 0;
}Output:
Adjacency List:
0 → [1, 2, 3]
1 → [0, 2]
2 → [0, 1, 3]
3 → [0, 2]
Edge (0,1) exists? Yes
Edge (1,3) exists? No
Neighbors of 2: 0 1 3So sánh: Matrix vs List
┌─────────────────────────────────────────────────────────────────┐
│ MATRIX vs LIST │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ADJACENCY MATRIX ADJACENCY LIST │
│ ───────────────── ─────────────── │
│ │
│ ┌───┬───┬───┬───┐ 0 → [1, 2, 3] │
│ │ 0 │ 1 │ 1 │ 1 │ 1 → [0, 2] │
│ ├───┼───┼───┼───┤ 2 → [0, 1, 3] │
│ │ 1 │ 0 │ 1 │ 0 │ 3 → [0, 2] │
│ ├───┼───┼───┼───┤ │
│ │ 1 │ 1 │ 0 │ 1 │ Space: O(V + E) │
│ ├───┼───┼───┼───┤ │
│ │ 1 │ 0 │ 1 │ 0 │ Edge check: O(degree) │
│ └───┴───┴───┴───┘ Get neighbors: O(1) │
│ │
│ Space: O(V²) │
│ Edge check: O(1) │
│ Get neighbors: O(V) │
│ │
└─────────────────────────────────────────────────────────────────┘Comparison Table
| Operation | Matrix | List |
|---|---|---|
| Space | O(V²) | O(V + E) |
| Add Edge | O(1) | O(1) |
| Remove Edge | O(1) | O(degree) |
| Check Edge | O(1) ✅ | O(degree) |
| Get Neighbors | O(V) | O(1) ✅ |
| Iterate All Edges | O(V²) | O(V + E) ✅ |
Khi nào dùng cái nào?
| Graph Type | Best Choice | Reason |
|---|---|---|
| Dense (E ≈ V²) | Matrix | Space ~V² anyway |
| Sparse (E << V²) | List | Save memory |
| Frequent edge check | Matrix | O(1) lookup |
| Frequent neighbor iteration | List | O(1) access |
| Small graphs (V < 1000) | Either | Both work fine |
💡 Rule of Thumb
Adjacency List là lựa chọn mặc định trong hầu hết các bài toán vì đồ thị thực tế thường sparse (ít cạnh so với số đỉnh).
Weighted Graph
Matrix với trọng số
cpp
// Thay 0/1 bằng weight
// INF = vô cực (không có cạnh)
const int INF = 1e9;
std::vector<std::vector<int>> matrix(V, std::vector<int>(V, INF));
// Add weighted edge
void addEdge(int u, int v, int weight) {
matrix[u][v] = weight;
matrix[v][u] = weight;
}List với trọng số
cpp
// Dùng pair<neighbor, weight>
std::vector<std::vector<std::pair<int, int>>> adjList(V);
// Add weighted edge
void addEdge(int u, int v, int weight) {
adjList[u].push_back({v, weight});
adjList[v].push_back({u, weight});
} WEIGHTED GRAPH
──────────────
5
0 ─────── 1
│ \ │
2 │ \ 3 │ 4
│ \ │
3 ─────── 2
1
List representation:
0 → [(1,5), (2,3), (3,2)]
1 → [(0,5), (2,4)]
2 → [(0,3), (1,4), (3,1)]
3 → [(0,2), (2,1)]Complete Implementation
cpp
#include <iostream>
#include <vector>
#include <utility>
// Weighted Undirected Graph using Adjacency List
class Graph {
int V;
std::vector<std::vector<std::pair<int, int>>> adjList; // {neighbor, weight}
public:
explicit Graph(int vertices) : V(vertices) {
adjList.resize(V);
}
void addEdge(int u, int v, int weight = 1) {
adjList[u].push_back({v, weight});
adjList[v].push_back({u, weight}); // Remove for directed
}
const std::vector<std::pair<int, int>>& neighbors(int v) const {
return adjList[v];
}
int getV() const { return V; }
void print() const {
for (int i = 0; i < V; ++i) {
std::cout << i << " → ";
for (auto [neighbor, weight] : adjList[i]) {
std::cout << "(" << neighbor << ", w=" << weight << ") ";
}
std::cout << "\n";
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 3);
g.addEdge(0, 3, 2);
g.addEdge(1, 2, 4);
g.addEdge(2, 3, 1);
g.print();
return 0;
}📚 Tổng kết
| Representation | Space | Edge Check | Best For |
|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | Dense graphs, frequent edge checks |
| Adjacency List | O(V+E) | O(degree) | Sparse graphs, traversals |
➡️ Tiếp theo
Bây giờ bạn đã biết cách lưu trữ đồ thị, hãy học cách duyệt nó!
BFS → — Breadth-First Search, duyệt theo từng tầng.