Giao diện
🌊 BFS — Breadth-First Search
BFS duyệt đồ thị theo từng tầng — thăm tất cả đỉnh cách gốc 1 bước trước, rồi mới đến 2 bước, 3 bước...
Analogy: Sóng nước lan tỏa
┌─────────────────────────────────────────────────────────────────┐
│ WATER RIPPLE ANALOGY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Thả viên đá xuống ao: │
│ │
│ ∙∙∙∙∙∙∙∙∙ │
│ ∙∙∙ ∙∙∙ │
│ ∙∙ ∙∙∙∙∙ ∙∙ │
│ ∙ ∙∙∙ ∙∙∙ ∙ │
│ ∙ ∙∙ ●●● ∙∙ ∙ ● = Điểm bắt đầu │
│ ∙ ∙∙∙ ∙∙∙ ∙ ∙ = Sóng lan ra │
│ ∙∙ ∙∙∙∙∙ ∙∙ │
│ ∙∙∙ ∙∙∙ │
│ ∙∙∙∙∙∙∙∙∙ │
│ │
│ BFS cũng vậy: Lan ra từ điểm bắt đầu, tầng này xong mới │
│ đến tầng tiếp theo. │
│ │
└─────────────────────────────────────────────────────────────────┘BFS Concept
Graph mẫu
SAMPLE GRAPH
────────────
0
/|\
/ | \
1 2 3
/| |
4 5 6
BFS từ 0: 0 → 1, 2, 3 → 4, 5, 6
Level 0: {0}
Level 1: {1, 2, 3}
Level 2: {4, 5, 6}Algorithm
- Bắt đầu từ đỉnh nguồn, đánh dấu đã thăm, đưa vào queue
- Lấy đỉnh đầu queue ra
- Thăm tất cả đỉnh kề chưa thăm, đánh dấu, đưa vào queue
- Lặp lại bước 2-3 cho đến khi queue rỗng
Step-by-step Visualization
┌─────────────────────────────────────────────────────────────────┐
│ BFS STEP-BY-STEP │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Graph: 0 │
│ /|\ │
│ 1 2 3 │
│ /| | │
│ 4 5 6 │
│ │
│ ───────────────────────────────────────────────────────────── │
│ │
│ Step 1: Start at 0 │
│ Queue: [0] Visited: {0} Output: 0 │
│ │
│ Step 2: Pop 0, add neighbors 1, 2, 3 │
│ Queue: [1, 2, 3] Visited: {0,1,2,3} Output: 0,1,2,3 │
│ │
│ Step 3: Pop 1, add neighbors 4, 5 │
│ Queue: [2, 3, 4, 5] Visited: {0,1,2,3,4,5} Output: 0,1,2,3,4,5│
│ │
│ Step 4: Pop 2 (no new neighbors) │
│ Queue: [3, 4, 5] (unchanged) │
│ │
│ Step 5: Pop 3, add neighbor 6 │
│ Queue: [4, 5, 6] Visited: {all} Output: ...,6 │
│ │
│ Step 6: Pop 4, 5, 6 (no new neighbors) │
│ Queue: [] Done! │
│ │
│ Final: 0 → 1 → 2 → 3 → 4 → 5 → 6 │
│ │
└─────────────────────────────────────────────────────────────────┘Implementation với std::queue
cpp
#include <iostream>
#include <vector>
#include <queue>
class Graph {
int V;
std::vector<std::vector<int>> adjList;
public:
explicit Graph(int vertices) : V(vertices) {
adjList.resize(V);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // Undirected
}
// BFS traversal from source vertex
void BFS(int source) {
// Track visited vertices
std::vector<bool> visited(V, false);
// Queue for BFS
std::queue<int> q;
// Start with source
visited[source] = true;
q.push(source);
std::cout << "BFS from " << source << ": ";
while (!q.empty()) {
// Dequeue front vertex
int current = q.front();
q.pop();
std::cout << current << " ";
// Visit all adjacent vertices
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
std::cout << "\n";
}
};
int main() {
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 4);
g.addEdge(1, 5);
g.addEdge(3, 6);
g.BFS(0); // Output: BFS from 0: 0 1 2 3 4 5 6
return 0;
}BFS with Level Tracking
cpp
// BFS that tracks level/distance from source
void BFS_with_levels(int source) {
std::vector<bool> visited(V, false);
std::vector<int> level(V, -1); // -1 = not visited
std::queue<int> q;
visited[source] = true;
level[source] = 0;
q.push(source);
while (!q.empty()) {
int current = q.front();
q.pop();
std::cout << "Node " << current << " at level " << level[current] << "\n";
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
level[neighbor] = level[current] + 1; // One step further
q.push(neighbor);
}
}
}
}Output:
Node 0 at level 0
Node 1 at level 1
Node 2 at level 1
Node 3 at level 1
Node 4 at level 2
Node 5 at level 2
Node 6 at level 2Shortest Path (Unweighted)
BFS tìm đường đi ngắn nhất trong đồ thị unweighted:
cpp
// Find shortest path from source to all vertices
std::vector<int> shortestPath(int source) {
std::vector<int> dist(V, -1); // -1 = unreachable
std::vector<int> parent(V, -1); // For path reconstruction
std::queue<int> q;
dist[source] = 0;
q.push(source);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int neighbor : adjList[current]) {
if (dist[neighbor] == -1) { // Not visited
dist[neighbor] = dist[current] + 1;
parent[neighbor] = current;
q.push(neighbor);
}
}
}
return dist;
}
// Reconstruct path from source to target
std::vector<int> getPath(int source, int target, const std::vector<int>& parent) {
std::vector<int> path;
for (int v = target; v != -1; v = parent[v]) {
path.push_back(v);
}
std::reverse(path.begin(), path.end());
return path;
}Connected Components
cpp
// Find all connected components
std::vector<std::vector<int>> findComponents() {
std::vector<bool> visited(V, false);
std::vector<std::vector<int>> components;
for (int i = 0; i < V; ++i) {
if (!visited[i]) {
// Start new component
std::vector<int> component;
std::queue<int> q;
visited[i] = true;
q.push(i);
while (!q.empty()) {
int current = q.front();
q.pop();
component.push_back(current);
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
components.push_back(component);
}
}
return components;
}BFS Applications
| Application | Description |
|---|---|
| Shortest Path | Đường đi ngắn nhất (unweighted) |
| Level/Distance | Tính khoảng cách từ nguồn |
| Connected Components | Tìm các thành phần liên thông |
| Bipartite Check | Kiểm tra đồ thị 2 phần |
| Cycle Detection | Phát hiện chu trình |
| Web Crawler | Crawl theo từng level |
Complexity Analysis
┌─────────────────────────────────────────────────────────────────┐
│ BFS COMPLEXITY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ TIME COMPLEXITY: O(V + E) │
│ ───────────────────────── │
│ • Mỗi vertex được thăm đúng 1 lần: O(V) │
│ • Mỗi edge được xét đúng 1 lần: O(E) │
│ │
│ SPACE COMPLEXITY: O(V) │
│ ────────────────────── │
│ • visited array: O(V) │
│ • queue: O(V) worst case │
│ │
└─────────────────────────────────────────────────────────────────┘Complete Example
cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
class Graph {
int V;
std::vector<std::vector<int>> adj;
public:
explicit Graph(int v) : V(v), adj(v) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void BFS(int source) {
std::vector<bool> visited(V, false);
std::queue<int> q;
visited[source] = true;
q.push(source);
std::cout << "BFS: ";
while (!q.empty()) {
int curr = q.front();
q.pop();
std::cout << curr << " ";
for (int next : adj[curr]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
std::cout << "\n";
}
std::vector<int> shortestPath(int src, int dest) {
std::vector<int> dist(V, -1), parent(V, -1);
std::queue<int> q;
dist[src] = 0;
q.push(src);
while (!q.empty()) {
int curr = q.front();
q.pop();
if (curr == dest) break;
for (int next : adj[curr]) {
if (dist[next] == -1) {
dist[next] = dist[curr] + 1;
parent[next] = curr;
q.push(next);
}
}
}
// Reconstruct path
std::vector<int> path;
for (int v = dest; v != -1; v = parent[v]) {
path.push_back(v);
}
std::reverse(path.begin(), path.end());
return path;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.BFS(0);
auto path = g.shortestPath(0, 5);
std::cout << "Shortest path 0 → 5: ";
for (int v : path) {
std::cout << v << " ";
}
std::cout << "(length: " << path.size() - 1 << ")\n";
return 0;
}Output:
BFS: 0 1 2 3 4 5
Shortest path 0 → 5: 0 1 3 4 5 (length: 4)📚 Tổng kết
| Aspect | BFS |
|---|---|
| Data Structure | Queue (FIFO) |
| Exploration | Level-by-level |
| Shortest Path | ✅ (unweighted) |
| Time | O(V + E) |
| Space | O(V) |
➡️ Tiếp theo
BFS duyệt theo chiều rộng. Còn DFS thì đi sâu trước khi quay lại...
DFS → — Depth-First Search, đi sâu vào mê cung.