Giao diện
🔍 DFS — Depth-First Search
DFS đi sâu nhất có thể trước khi quay lại — giống như khám phá mê cung.
Analogy: Khám phá mê cung
┌─────────────────────────────────────────────────────────────────┐
│ MAZE EXPLORATION ANALOGY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌───┬───┬───┬───┬───┐ │
│ │ S │ │ │ │ │ S = Start (Bắt đầu) │
│ ├───┼───┼───┼───┼───┤ E = End (Đích) │
│ │ ↓ │███│ │███│ │ █ = Tường │
│ ├───┼───┼───┼───┼───┤ → = Đường đi │
│ │ ↓ │ │ │ │ │ │
│ ├───┼───┼───┼───┼───┤ DFS: Đi thẳng đến khi đụng tường, │
│ │ ↓ │███│███│ │ │ rồi quay lại thử đường khác │
│ ├───┼───┼───┼───┼───┤ │
│ │ → │ → │ → │ → │ E │ │
│ └───┴───┴───┴───┴───┘ │
│ │
│ Bạn đi vào mê cung, cứ đi sâu vào một ngõ. │
│ Nếu đụng ngõ cụt → quay lại ngã rẽ trước và thử đường khác. │
│ │
└─────────────────────────────────────────────────────────────────┘DFS Concept
Graph mẫu
SAMPLE GRAPH
────────────
0
/|\
/ | \
1 2 3
/| |
4 5 6
DFS từ 0 (go left first):
0 → 1 → 4 → 5 → 2 → 3 → 6
Đi sâu vào 1 trước, rồi 4, 5
Quay lại 0, đi 2
Quay lại 0, đi 3 → 6Algorithm
- Bắt đầu từ đỉnh nguồn, đánh dấu đã thăm
- Với mỗi đỉnh kề chưa thăm, đệ quy DFS
- Khi hết đỉnh kề chưa thăm, quay lại
Step-by-step Visualization
┌─────────────────────────────────────────────────────────────────┐
│ DFS STEP-BY-STEP │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Graph: 0 Stack visualization: │
│ /|\ │
│ 1 2 3 [0] │
│ /| | [0, 1] │
│ 4 5 6 [0, 1, 4] │
│ [0, 1] ← backtrack │
│ ───────────────────────────────── [0, 1, 5] │
│ [0, 1] ← backtrack │
│ Step 1: Visit 0 [0] ← backtrack │
│ Step 2: Visit 1 (first neighbor) [0, 2] │
│ Step 3: Visit 4 (first of 1) [0] ← backtrack │
│ Step 4: Backtrack to 1 [0, 3] │
│ Step 5: Visit 5 (second of 1) [0, 3, 6] │
│ Step 6: Backtrack to 1, then 0 [] ← done │
│ Step 7: Visit 2 │
│ Step 8: Backtrack to 0 │
│ Step 9: Visit 3 │
│ Step 10: Visit 6 │
│ │
│ Final: 0 → 1 → 4 → 5 → 2 → 3 → 6 │
│ │
└─────────────────────────────────────────────────────────────────┘Recursive Implementation
cpp
#include <iostream>
#include <vector>
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
}
// DFS helper function (recursive)
void DFS_util(int vertex, std::vector<bool>& visited) {
// Mark current vertex as visited
visited[vertex] = true;
std::cout << vertex << " ";
// Recursively visit all adjacent vertices
for (int neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
DFS_util(neighbor, visited);
}
}
}
// DFS traversal from source vertex
void DFS(int source) {
std::vector<bool> visited(V, false);
std::cout << "DFS from " << source << ": ";
DFS_util(source, visited);
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.DFS(0); // Output: DFS from 0: 0 1 4 5 2 3 6
return 0;
}Iterative Implementation với std::stack
cpp
#include <iostream>
#include <vector>
#include <stack>
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);
}
// DFS using stack (iterative)
void DFS_iterative(int source) {
std::vector<bool> visited(V, false);
std::stack<int> s;
s.push(source);
std::cout << "DFS (iterative) from " << source << ": ";
while (!s.empty()) {
int current = s.top();
s.pop();
// Skip if already visited
if (visited[current]) continue;
// Mark as visited and process
visited[current] = true;
std::cout << current << " ";
// Push all unvisited neighbors (reverse order for same order as recursive)
for (auto it = adjList[current].rbegin(); it != adjList[current].rend(); ++it) {
if (!visited[*it]) {
s.push(*it);
}
}
}
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.DFS_iterative(0);
return 0;
}💡 Recursive vs Iterative
- Recursive: Code đẹp hơn, dễ hiểu
- Iterative: Không bị stack overflow với graph lớn
BFS vs DFS Comparison
┌─────────────────────────────────────────────────────────────────┐
│ BFS vs DFS │
├─────────────────────────────────────────────────────────────────┤
│ │
│ BFS DFS │
│ ─── ─── │
│ │
│ Level 0: [0] Visit: 0 │
│ / \ | │
│ Level 1: [1] [2] Visit: 1 │
│ | | | │
│ Level 2: [3] [4] Visit: 3 │
│ | │
│ Order: 0, 1, 2, 3, 4 Visit: 4 (backtrack) │
│ | │
│ Queue: ──►──►──►──► Visit: 2 │
│ (FIFO: First In First Out) | │
│ Order: 0, 1, 3, 4, 2 │
│ │
│ Stack: ─▼─▲─▼─▲─ │
│ (LIFO: Last In First Out) │
│ │
└─────────────────────────────────────────────────────────────────┘| Aspect | BFS | DFS |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) |
| Exploration | Level-by-level | Depth-first |
| Shortest Path | ✅ (unweighted) | ❌ |
| Memory | O(width) | O(depth) |
| Best for | Shortest path, levels | Path finding, cycles |
DFS Applications
1. Cycle Detection
cpp
// Detect cycle in undirected graph
bool hasCycle_util(int v, int parent, std::vector<bool>& visited) {
visited[v] = true;
for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
if (hasCycle_util(neighbor, v, visited)) {
return true;
}
}
// If visited and not parent → cycle found
else if (neighbor != parent) {
return true;
}
}
return false;
}
bool hasCycle() {
std::vector<bool> visited(V, false);
for (int i = 0; i < V; ++i) {
if (!visited[i]) {
if (hasCycle_util(i, -1, visited)) {
return true;
}
}
}
return false;
}2. Path Finding
cpp
// Find if path exists from source to destination
bool pathExists_util(int current, int dest, std::vector<bool>& visited) {
if (current == dest) return true;
visited[current] = true;
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
if (pathExists_util(neighbor, dest, visited)) {
return true;
}
}
}
return false;
}
bool pathExists(int src, int dest) {
std::vector<bool> visited(V, false);
return pathExists_util(src, dest, visited);
}3. All Paths from Source to Destination
cpp
void findAllPaths_util(int current, int dest,
std::vector<int>& path,
std::vector<std::vector<int>>& allPaths,
std::vector<bool>& visited) {
visited[current] = true;
path.push_back(current);
if (current == dest) {
allPaths.push_back(path);
} else {
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
findAllPaths_util(neighbor, dest, path, allPaths, visited);
}
}
}
// Backtrack
path.pop_back();
visited[current] = false;
}
std::vector<std::vector<int>> findAllPaths(int src, int dest) {
std::vector<std::vector<int>> allPaths;
std::vector<int> path;
std::vector<bool> visited(V, false);
findAllPaths_util(src, dest, path, allPaths, visited);
return allPaths;
}DFS Applications Summary
| Application | Description |
|---|---|
| Cycle Detection | Phát hiện chu trình |
| Path Finding | Kiểm tra đường đi tồn tại |
| All Paths | Tìm tất cả đường đi |
| Topological Sort | Sắp xếp topo (DAG) |
| Connected Components | Thành phần liên thông |
| Strongly Connected | SCC trong directed graph |
| Maze Solving | Giải mê cung |
Complexity Analysis
┌─────────────────────────────────────────────────────────────────┐
│ DFS COMPLEXITY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ TIME COMPLEXITY: O(V + E) │
│ ───────────────────────── │
│ • Same as BFS — mỗi vertex và edge được xét 1 lần │
│ │
│ SPACE COMPLEXITY: │
│ ───────────────── │
│ • Recursive: O(V) cho call stack │
│ • Iterative: O(V) cho explicit stack │
│ • visited array: O(V) │
│ │
│ Note: Recursive có thể gây Stack Overflow với graph rất sâu │
│ │
└─────────────────────────────────────────────────────────────────┘Complete Example
cpp
#include <iostream>
#include <vector>
#include <stack>
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);
}
// Recursive DFS
void DFS_recursive(int v, std::vector<bool>& vis) {
vis[v] = true;
std::cout << v << " ";
for (int n : adj[v]) {
if (!vis[n]) DFS_recursive(n, vis);
}
}
void DFS(int src) {
std::vector<bool> vis(V, false);
std::cout << "DFS (recursive): ";
DFS_recursive(src, vis);
std::cout << "\n";
}
// Iterative DFS
void DFS_iter(int src) {
std::vector<bool> vis(V, false);
std::stack<int> s;
s.push(src);
std::cout << "DFS (iterative): ";
while (!s.empty()) {
int curr = s.top();
s.pop();
if (vis[curr]) continue;
vis[curr] = true;
std::cout << curr << " ";
for (auto it = adj[curr].rbegin(); it != adj[curr].rend(); ++it) {
if (!vis[*it]) s.push(*it);
}
}
std::cout << "\n";
}
// Cycle detection
bool hasCycle_util(int v, int parent, std::vector<bool>& vis) {
vis[v] = true;
for (int n : adj[v]) {
if (!vis[n]) {
if (hasCycle_util(n, v, vis)) return true;
} else if (n != parent) {
return true;
}
}
return false;
}
bool hasCycle() {
std::vector<bool> vis(V, false);
for (int i = 0; i < V; ++i) {
if (!vis[i] && hasCycle_util(i, -1, vis)) return true;
}
return false;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.DFS(0);
g.DFS_iter(0);
std::cout << "Has cycle? " << (g.hasCycle() ? "Yes" : "No") << "\n";
// Add edge to create cycle
g.addEdge(4, 5);
std::cout << "After adding edge (4,5): Has cycle? "
<< (g.hasCycle() ? "Yes" : "No") << "\n";
return 0;
}Output:
DFS (recursive): 0 1 3 5 2 4
DFS (iterative): 0 1 3 5 2 4
Has cycle? No
After adding edge (4,5): Has cycle? Yes📚 Tổng kết
| Aspect | DFS |
|---|---|
| Data Structure | Stack (explicit or call stack) |
| Exploration | Depth-first |
| Implementation | Recursive or Iterative |
| Time | O(V + E) |
| Space | O(V) |
| Best for | Cycle detection, path finding, backtracking |
🎯 Module 6 Part 1 Complete!
Chúc mừng! Bạn đã hoàn thành Part 1: Representation & Traversal:
- ✅ Graph Representation (Matrix vs List)
- ✅ BFS (Breadth-First Search)
- ✅ DFS (Depth-First Search)
Coming in Part 2:
- Dijkstra's Shortest Path
- Minimum Spanning Tree
- Topological Sort