Câu lạc bộ Tin học dành cho học sinh Tiểu học

[sai mần gium pen 07 - Vũ Hoàng Quân 5/4]

Mục tiêu:​

• Hiểu khái niệm đồ thị (graph) – nền tảng của rất nhiều bài toán thực tế (đường đi, mạng xã hội, kết nối, game map, v.v.).
• Biết cách duyệt đồ thị bằng BFS và DFS.
• Áp dụng thuật toán để tìm đường đi ngắn nhất (trong bản đồ, mê cung, v.v.)

---

1. Đồ thị là gì?​

• Đồ thị (graph) gồm đỉnh (node) và cạnh (edge).
• Biểu diễn mối quan hệ giữa các phần tử: ví dụ bạn bè trên Facebook, các thành phố nối với nhau bằng đường.

---

2. Cách lưu trữ đồ thị​

Cách : Danh sách kề (Adjacency List)​

vector<int> graph[100];

Ví dụ:
Giả sử có 4 đỉnh, với các cạnh:

• 1 nối 2, 3
• 2 nối 4

graph[1] = {2, 3};
graph[2] = {1, 4};
graph[3] = {1};
graph[4] = {2};

---

3. Thuật toán DFS (Depth-First Search)​

Duyệt sâu – đi hết một nhánh rồi mới quay lại.




#include <bits/stdc++.h>
using namespace std;


vector<int> graph[100];
bool visited[100];


void dfs(int u) {
visited = true;
cout << u << " ";
for (int v : graph)
if (!visited[v]) dfs(v);
}


int main() {
int n = 4;
graph[1] = {2, 3};
graph[2] = {1, 4};
graph[3] = {1};
graph[4] = {2};


cout << "Duyet DFS tu dinh 1: ";
dfs(1);
}

Kết quả:




Duyet DFS tu dinh 1: 1 2 4 3

---

4. Thuật toán BFS (Breadth-First Search)​

Duyệt rộng – duyệt từng lớp, như gợn sóng lan ra.
#include <bits/stdc++.h>
using namespace std;


vector<int> graph[100];
bool visited[100];


void bfs(int start) {
queue<int> q;
q.push(start);
visited[start] = true;


while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " ";


for (int v : graph) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}


int main() {
graph[1] = {2, 3};
graph[2] = {1, 4};
graph[3] = {1};
graph[4] = {2};


cout << "Duyet BFS tu dinh 1: ";
bfs(1);
}

Kết quả:
Duyet BFS tu dinh 1: 1 2 3 4

---

5. Ứng dụng thực tế – Tìm đường đi trong mê cung (Shortest Path)​

Mô phỏng mê cung:

S . . #
. # . .
. . . E

BFS có thể tìm đường ngắn nhất từ S → E
→ Giống như AI tìm đường trong game, hoặc GPS tìm đường ngắn nhất.

---

Hình minh họa: DFS vs BFS​

1
/ \
2 3
|
4

DFS: 1 → 2 → 4 → 3
BFS: 1 → 2 → 3 → 4


DFS đi “sâu” trước
BFS đi “rộng” trước

---

Bài tập nâng cao:​

Viết chương trình tìm đường đi ngắn nhất từ đỉnh A đến B trong đồ thị không trọng số bằng BFS.