Duyệt đồ thị — BFS, DFS & Dijkstra

Mỗi khi bạn mở Google Maps, mỗi khi Facebook gợi ý "People You May Know", mỗi khi Netflix đề xuất phim — graph algorithms đang chạy phía sau. Ba thuật toán trong bài này — BFS, DFS, và Dijkstra — là nền tảng xử lý đồ thị mà mọi kỹ sư phải nắm vững. BFS và DFS duyệt graph, Dijkstra tìm đường ngắn nhất. Đơn giản thế thôi — nhưng cách implement đúng mới là thử thách.

🎯 Mục tiêu

🎯 Sau bài này, bạn sẽ:

Phân biệt BFS (queue, level-by-level) và DFS (stack/recursion, go-deep)
Implement BFS tìm shortest path trên unweighted graph
Implement DFS cho cycle detection và connected components
Implement Dijkstra với đúng tư duy priority queue
Biết tại sao negative weights phá vỡ Dijkstra

Bức tranh tư duy — 3 cách khám phá mê cung

Tưởng tượng bạn đứng trước một mê cung khổng lồ. Có ba chiến thuật khám phá:

BFS — Sóng nước lan: Bạn đứng giữa hồ ném đá, sóng lan đều ra mọi hướng theo từng vòng (level-by-level). Vòng 1 cách 1 bước, vòng 2 cách 2 bước... Sóng chạm tường trước → đó là lối thoát gần nhất.
DFS — Thám hiểm hang động: Bạn cầm đuốc đi sâu hết một nhánh, cụt thì quay lại (backtrack) rồi thử nhánh khác. Bạn sẽ khám phá hết mọi ngóc ngách, nhưng không đảm bảo tìm đường ngắn nhất.
Dijkstra — Lửa cháy rừng có tốc độ khác nhau: Mỗi con đường có "sức cản" khác nhau (weight). Lửa lan qua đường nhẹ (weight nhỏ) nhanh hơn. Luôn cháy đến điểm gần nhất trước — đó chính là greedy strategy.

💡 Ghi nhớ nhanh

BFS = Queue = Level-by-level = Shortest path (unweighted). DFS = Stack = Go deep = Backtrack. Dijkstra = Priority Queue = Greedy = Shortest path (weighted, non-negative).

Graph mẫu — dùng xuyên suốt bài

Để dễ theo dõi, tất cả ví dụ trong bài đều dùng cùng một graph:

Graph Example (weighted, undirected):

    A ---4--- B
    |       / |
    2     3   6
    |   /     |
    C ---1--- D ---5--- E

Adjacency List:
A: [(B,4), (C,2)]
B: [(A,4), (C,3), (D,6)]
C: [(A,2), (B,3), (D,1)]
D: [(B,6), (C,1), (E,5)]
E: [(D,5)]

Khi chạy BFS/DFS, ta bỏ qua weight (coi mọi cạnh bằng nhau). Khi chạy Dijkstra, ta dùng weight.

BFS — Breadth-First Search

Cơ chế hoạt động

BFS dùng queue (FIFO) — ai vào trước xử lý trước: đưa source vào queue → dequeue node → enqueue neighbors chưa visited → lặp lại. Key guarantee: BFS tìm shortest path trên unweighted graph vì duyệt theo khoảng cách tăng dần.

ASCII Trace — BFS từ A

Start: A     Queue: [A]     Visited: {A}

Step 1: Dequeue A → neighbors B, C
  Queue: [B, C]       Visited: {A, B, C}
Step 2: Dequeue B → neighbors A✓, C✓, D
  Queue: [C, D]       Visited: {A, B, C, D}
Step 3: Dequeue C → all neighbors visited
  Queue: [D]          Visited: {A, B, C, D}
Step 4: Dequeue D → neighbors B✓, C✓, E
  Queue: [E]          Visited: {A, B, C, D, E}
Step 5: Dequeue E → D✓
  Queue: []           Visited: {A, B, C, D, E}

BFS order: A → B → C → D → E
Shortest distances (hops): A=0, B=1, C=1, D=2, E=3

Để ý: B và C cùng level 1, D ở level 2, E ở level 3. BFS luôn duyệt hết level hiện tại trước khi sang level tiếp.

Code — BFS

C++PythonJava

cpp

vector<int> bfs(int start, const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    vector<int> order;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return order;
}

python

from collections import deque

def bfs(graph: dict, start: str) -> list[str]:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

java

public static List<Integer> bfs(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> queue = new LinkedList<>();
    List<Integer> order = new ArrayList<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
    return order;
}

Độ phức tạp: $O (V + E)$ thời gian, $O (V)$ bộ nhớ — với $V$ = số đỉnh, $E$ = số cạnh.

BFS tìm shortest path (unweighted)

Muốn truy vết đường đi, thêm mảng parent — khi BFS tới node v qua u, ghi parent[v] = u. Sau đó truy ngược từ end về start:

python

def bfs_shortest_path(graph, start, end):
    visited = {start}
    queue = deque([start])
    parent = {start: None}
    while queue:
        node = queue.popleft()
        if node == end:
            break
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    # Truy vết ngược: end → ... → start → reverse
    path, cur = [], end
    while cur is not None:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]

Ứng dụng thực tế của BFS

Ứng dụng	Giải thích
Shortest path (unweighted)	Social network "degrees of separation"
Level-order traversal	Duyệt cây theo tầng
Web crawler	Crawl trang web theo level (breadth)
Flood fill	Paint bucket tool trong Photoshop
0-1 BFS	Cạnh weight 0 hoặc 1 — dùng deque thay queue

Visualizer States — BFS

VISUALIZER STATES — BFS:
State 1: START       — source node turns yellow
State 2: EXPLORE     — current node's edges glow, neighbors identified
State 3: ENQUEUE     — neighbor nodes turn light blue (in queue)
State 4: PROCESS     — dequeued node turns green (visited/finalized)
State 5: LEVEL_BOUND — visual separator between BFS levels
State 6: DONE        — all reachable nodes green

DFS — Depth-First Search

Cơ chế hoạt động

DFS dùng stack (LIFO) hoặc recursion (implicit stack): push source → pop node → mark visited → push neighbors → repeat. Luôn đi sâu nhất có thể trước khi backtrack.

ASCII Trace — DFS từ A (iterative)

Start: A    Stack: [A]    Visited: {}

Step 1: Pop A → mark visited, push C, B
  Stack: [C, B]         Visited: {A}        → Process A

Step 2: Pop B → mark visited, push D, C
  Stack: [C, D, C]      Visited: {A, B}     → Process B

Step 3: Pop C → mark visited, push D
  Stack: [C, D, D]      Visited: {A, B, C}  → Process C

Step 4: Pop D → mark visited, push E
  Stack: [C, D, E]      Visited: {A,B,C,D}  → Process D

Step 5: Pop E → mark visited
  Stack: [C, D]          Visited: {A,B,C,D,E} → Process E

Step 6-7: Pop D, C → already visited → skip

DFS order: A → B → C → D → E  (goes DEEP first!)

📌 Thứ tự duyệt DFS phụ thuộc vào thứ tự push neighbor

Nếu push neighbor theo thứ tự khác, kết quả DFS sẽ khác. Đây là điều bình thường — DFS không có thứ tự duy nhất.

Code — DFS Recursive

C++PythonJava

cpp

void dfs(int node, const vector<vector<int>>& adj,
         vector<bool>& visited, vector<int>& order) {
    visited[node] = true;
    order.push_back(node);
    for (int neighbor : adj[node])
        if (!visited[neighbor])
            dfs(neighbor, adj, visited, order);
}

python

def dfs_recursive(graph: dict, node: str, visited: set = None) -> list[str]:
    if visited is None:
        visited = set()
    visited.add(node)
    result = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))
    return result

java

public static void dfs(int node, List<List<Integer>> adj,
                       boolean[] visited, List<Integer> order) {
    visited[node] = true;
    order.add(node);
    for (int neighbor : adj.get(node))
        if (!visited[neighbor])
            dfs(neighbor, adj, visited, order);
}

Code — DFS Iterative (an toàn hơn cho graph lớn)

C++PythonJava

cpp

vector<int> dfs_iterative(int start, const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;
    vector<int> order;
    st.push(start);
    while (!st.empty()) {
        int node = st.top(); st.pop();
        if (visited[node]) continue;
        visited[node] = true;
        order.push_back(node);
        for (int i = adj[node].size() - 1; i >= 0; i--)
            if (!visited[adj[node][i]])
                st.push(adj[node][i]);
    }
    return order;
}

python

def dfs_iterative(graph: dict, start: str) -> list[str]:
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return order

java

public static List<Integer> dfsIterative(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    List<Integer> order = new ArrayList<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;
        order.add(node);
        List<Integer> neighbors = adj.get(node);
        for (int i = neighbors.size() - 1; i >= 0; i--)
            if (!visited[neighbors.get(i)])
                stack.push(neighbors.get(i));
    }
    return order;
}

⚠️ DFS recursive trên graph lớn → Stack Overflow

Graph 100.000 node, DFS recursive sẽ chết. Dùng iterative với explicit stack. Python mặc định recursion limit = 1000 — bạn có thể tăng bằng sys.setrecursionlimit() nhưng đó là band-aid, không phải giải pháp.

Ứng dụng thực tế của DFS

Ứng dụng	Giải thích
Cycle detection	Phát hiện vòng lặp trong dependency graph
Topological sort	Sắp xếp thứ tự build/compile (DAG)
Connected components	Đếm "đảo" trong grid, nhóm bạn bè
Maze solving	Tìm đường ra mê cung (backtracking)
Path existence	Kiểm tra có đường đi giữa 2 node không

Visualizer States — DFS

VISUALIZER STATES — DFS:
State 1: START     — source node turns yellow
State 2: EXPLORE   — go deep, current edge glows
State 3: VISIT     — node turns green (first visit)
State 4: DEAD_END  — node has no unvisited neighbors, turns dark green
State 5: BACKTRACK — dashed line back to parent (orange glow)
State 6: DONE      — all reachable nodes green

BFS vs DFS — Bảng so sánh quyết định

Tiêu chí	BFS	DFS
Data structure	Queue (FIFO)	Stack / Recursion (LIFO)
Thứ tự duyệt	Level-by-level	Go deep, then backtrack
Shortest path (unweighted)	✅ Đảm bảo	❌ Không đảm bảo
Memory	$O (w)$ — width, có thể lớn	$O (d)$ — depth, thường nhỏ
Complete?	✅ Duyệt hết reachable nodes	✅ Duyệt hết reachable nodes
Tốt cho	Shortest path, level-order	Cycle detection, topo sort
Graph rộng (high branching)	❌ Tốn memory	✅ Hiệu quả hơn
Graph sâu	✅ Không sợ depth	❌ Stack overflow có thể xảy ra
Complexity	$O (V + E)$	$O (V + E)$

💡 Quy tắc chọn nhanh

Cần shortest path? → BFS
Cần duyệt hết / detect cycle / topo sort? → DFS
Graph quá rộng, memory hạn chế? → DFS
Graph quá sâu? → BFS hoặc DFS iterative

Dijkstra — Đúng tư duy Priority Queue

Core Idea

"Luôn xử lý vertex có khoảng cách ngắn nhất mà chưa xử lý."

Dijkstra KHÔNG phải BFS với weights. Đây là greedy algorithm — mỗi bước chọn node gần nhất, commit khoảng cách đó là final, và relax các neighbor.

Quy trình:

dist[source] = 0, dist[mọi node khác] = ∞
Đưa source vào priority queue (min-heap)
Extract min — lấy node có dist nhỏ nhất
Relax neighbors: nếu dist[u] + weight(u,v) < dist[v] → cập nhật dist[v]
Lặp lại cho đến khi PQ rỗng

Full ASCII Trace — Dijkstra từ A

Initial: dist = {A:0, B:∞, C:∞, D:∞, E:∞}    PQ: [(0,A)]

Step 1: Extract (0,A) ← cheapest
  A→B: 0+4=4 < ∞ → dist[B]=4 ✓    A→C: 0+2=2 < ∞ → dist[C]=2 ✓
  PQ: [(2,C), (4,B)]    dist = {A:0, B:4, C:2, D:∞, E:∞}

Step 2: Extract (2,C) ← cheapest
  C→A: 2+2=4 > 0 → skip    C→B: 2+3=5 > 4 → skip
  C→D: 2+1=3 < ∞ → dist[D]=3 ✓
  PQ: [(3,D), (4,B)]    dist = {A:0, B:4, C:2, D:3, E:∞}

Step 3: Extract (3,D) ← cheapest
  D→B: 3+6=9 > 4 → skip    D→C: 3+1=4 > 2 → skip
  D→E: 3+5=8 < ∞ → dist[E]=8 ✓
  PQ: [(4,B), (8,E)]    dist = {A:0, B:4, C:2, D:3, E:8}

Step 4: Extract (4,B) — all neighbors have shorter paths → skip all
  PQ: [(8,E)]    dist unchanged

Step 5: Extract (8,E) — neighbor D visited → skip
  PQ: []    dist = {A:0, B:4, C:2, D:3, E:8}  ✅ DONE!

Shortest paths from A:
  A→A: 0 | A→C: 2 (A→C) | A→D: 3 (A→C→D) | A→B: 4 (A→B) | A→E: 8 (A→C→D→E)

Code — Dijkstra

C++PythonJava

cpp

vector<int> dijkstra(int source, const vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> visited(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dist[source] = 0;
    pq.push({0, source});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto [v, weight] : adj[u]) {
            if (!visited[v] && d + weight < dist[v]) {
                dist[v] = d + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

python

import heapq

def dijkstra(graph: dict, source: str) -> dict:
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    pq = [(0, source)]  # (distance, node)
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue  # Lazy deletion — bỏ qua entry cũ
        visited.add(u)
        for v, weight in graph[u]:
            if v not in visited and d + weight < dist[v]:
                dist[v] = d + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

java

public static int[] dijkstra(int source, List<List<int[]>> adj) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    boolean[] visited = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0]));
    dist[source] = 0;
    pq.offer(new int[]{0, source});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (visited[u]) continue;
        visited[u] = true;
        for (int[] edge : adj.get(u)) {
            int v = edge[0], weight = edge[1];
            if (!visited[v] && d + weight < dist[v]) {
                dist[v] = d + weight;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

Độ phức tạp: $O ((V + E) \log V)$ với binary heap. Mỗi node extract 1 lần, mỗi edge relax 1 lần — mỗi operation $O (\log V)$ .

Tại sao Negative Weights phá vỡ Dijkstra?

Dijkstra commit khoảng cách khi extract min — "đây là shortest, không thể cải thiện". Negative weight phá vỡ giả định đó:

Counter-example:

    A ---1--→ B
    |         |
    4        -3
    ↓         ↓
    C ←--------

Dijkstra từ A: Extract A → dist[B]=1, dist[C]=4.
Extract B (dist=1) → COMMITTED! Relax B→C: 1+(-3) = -2 < 4 ✓
Nhưng nếu có path A→C→...→B cost 3 → true dist[B]=0, KHÔNG PHẢI 1.
Dijkstra đã commit, không thể sửa!

❌ Dijkstra KHÔNG hoạt động với negative edge weights

Đây là câu trap phỏng vấn kinh điển. Nếu graph có negative weights, dùng Bellman-Ford ( $O (V E)$ ) hoặc SPFA. Nếu interviewer hỏi "Dijkstra có hoạt động với negative weights không?" → câu trả lời duy nhất đúng là KHÔNG.

Lazy Deletion vs Decrease-Key

Có 2 cách xử lý khi dist cải thiện:

Approach	Cách làm	Complexity	Khi nào dùng
Lazy deletion	Push entry mới vào PQ, skip entry cũ khi pop	$O ((V + E) \log E)$	Interview, competitive programming
Decrease-key	Update priority in-place (indexed PQ)	$O ((V + E) \log V)$ strict	Production systems cần tối ưu

💡 Lời khuyên cho phỏng vấn

Dùng lazy deletion — code ngắn, dễ hiểu, đủ nhanh. Nếu interviewer hỏi optimize, nhắc đến decrease-key với indexed priority queue (Fibonacci heap cho $O (V \log V + E)$ — chỉ cần biết lý thuyết, không cần implement).

Visualizer States — Dijkstra

VISUALIZER STATES — Dijkstra:
State 1: INIT        — source green (dist=0), others gray (dist=∞)
State 2: EXTRACT_MIN — cheapest node in PQ pulses yellow
State 3: RELAX       — edge being relaxed glows, target updates distance label
State 4: UPDATE_PQ   — priority queue shown as sorted list (side panel)
State 5: FINALIZE    — node turns green (shortest path confirmed)
State 6: SKIP        — relaxation skipped (no improvement), brief red flash
State 7: DONE        — all nodes green with final distances displayed

Sai lầm điển hình — Tránh ngay!

#	Sai lầm	Hậu quả	Cách fix
1	❌ Quên `visited` set trong BFS/DFS	Infinite loop trên cyclic graph	Luôn check visited trước khi enqueue/push
2	❌ Dùng Dijkstra cho negative weights	Kết quả sai	Dùng Bellman-Ford hoặc SPFA
3	❌ BFS dùng stack, DFS dùng queue	Kết quả ngược hoàn toàn	BFS = Queue, DFS = Stack — học thuộc!
4	❌ Dijkstra thiếu `if u in visited: continue`	Xử lý lại node đã finalize, chậm + sai	Luôn skip node đã visited
5	❌ DFS recursive trên graph lớn ( $V > 10^{4}$ )	Stack overflow	Dùng DFS iterative

Practice

🧠 Quiz — BFS Order

🧠 Quiz

Câu hỏi: Chạy BFS từ node A trên graph mẫu (unweighted), thứ tự duyệt là gì?

[x] A. A → B → C → D → E
[ ] B. A → C → D → B → E
[ ] C. A → B → D → C → E
[ ] D. A → C → B → D → E Giải thích: BFS duyệt level-by-level. A (level 0) → B, C (level 1, theo thứ tự adjacency list) → D (level 2) → E (level 3). Đáp án A đúng vì B xuất hiện trước C trong adjacency list của A.

🧠 Quiz — Dijkstra

🧠 Quiz

Câu hỏi: Dijkstra từ A, shortest distance tới E là bao nhiêu?

[ ] A. 5
[ ] B. 10
[x] C. 8
[ ] D. 9 Giải thích: Đường ngắn nhất: A→C (2) → C→D (1) → D→E (5) = 2 + 1 + 5 = 8. Không phải A→B→D→E = 4 + 6 + 5 = 15 hay bất kỳ path nào khác.

🐛 Spot the Bug — Dijkstra thiếu lazy deletion

🐛 Spot-the-Bug

Dijkstra bị lỗi — Python

python

import heapq

def dijkstra_buggy(graph, source):
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        # BUG: thiếu gì ở đây?
        for v, weight in graph[u]:
            if d + weight < dist[v]:
                dist[v] = d + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

Câu hỏi: Code trên thiếu 1 dòng quan trọng. Nếu không có dòng đó, thuật toán vẫn cho kết quả đúng nhưng chậm hơn rất nhiều trên graph lớn. Dòng đó là gì?

Đáp án: Thiếu kiểm tra lazy deletion:

python

if u in visited:
    continue
visited.add(u)

Không có check này, mỗi node có thể bị xử lý nhiều lần (mỗi lần dist cải thiện). Trên graph dày đặc, complexity tệ nhất tăng từ $O ((V + E) \log V)$ lên $O (V^{2} \log V)$ .

🧩 Parsons Problem — Sắp xếp code BFS

🧩 Parsons Problem

Sắp xếp đúng thứ tự các dòng code BFS

Cho các dòng code dưới đây, sắp xếp đúng thứ tự để hoàn thành hàm BFS:

queue = deque([start])
while queue:
visited = {start}
node = queue.popleft()
if neighbor not in visited:
for neighbor in graph[node]:
order.append(node)
visited.add(neighbor)
queue.append(neighbor)
order = []

Thứ tự đúng: 3, 1, 10, 2, 4, 7, 6, 5, 8, 9

Tổng kết — So sánh 3 thuật toán

	BFS	DFS	Dijkstra
Data structure	Queue	Stack	Priority Queue (min-heap)
Strategy	Level-by-level	Go deep first	Greedy (cheapest first)
Shortest path	✅ Unweighted	❌	✅ Weighted (non-negative)
Complexity	$O (V + E)$	$O (V + E)$	$O ((V + E) \log V)$
Negative weights	N/A	N/A	❌ Không hoạt động
Use case chính	Level-order, shortest hops	Cycle detect, topo sort	GPS, network routing

✅ Checklist triển khai

BFS

[ ] Hiểu queue FIFO và level-by-level traversal
[ ] Implement BFS với visited set đúng cách
[ ] Dùng BFS tìm shortest path (unweighted) bằng mảng parent
[ ] Biết BFS applications: flood fill, 0-1 BFS, web crawler

DFS

[ ] Hiểu stack/recursion và backtracking
[ ] Implement cả recursive và iterative DFS
[ ] Biết khi nào dùng iterative (graph lớn, tránh stack overflow)
[ ] Biết DFS applications: cycle detection, topological sort

Dijkstra

[ ] Hiểu greedy strategy: extract min → relax → commit
[ ] Implement với priority queue + lazy deletion
[ ] Trace được Dijkstra trên paper (ít nhất 5 nodes)
[ ] Giải thích được tại sao negative weights phá vỡ Dijkstra
[ ] Biết sự khác nhau lazy deletion vs decrease-key

📍 Trang tiếp theo: Dynamic Programming Intro →

Duyệt đồ thị — BFS, DFS & Dijkstra ​

Bức tranh tư duy — 3 cách khám phá mê cung ​

Graph mẫu — dùng xuyên suốt bài ​

BFS — Breadth-First Search ​

Cơ chế hoạt động ​

ASCII Trace — BFS từ A ​

Code — BFS ​

BFS tìm shortest path (unweighted) ​

Ứng dụng thực tế của BFS ​

Visualizer States — BFS ​

DFS — Depth-First Search ​

Cơ chế hoạt động ​

ASCII Trace — DFS từ A (iterative) ​

Code — DFS Recursive ​

Code — DFS Iterative (an toàn hơn cho graph lớn) ​

Ứng dụng thực tế của DFS ​

Visualizer States — DFS ​

BFS vs DFS — Bảng so sánh quyết định ​

Dijkstra — Đúng tư duy Priority Queue ​

Core Idea ​

Full ASCII Trace — Dijkstra từ A ​

Code — Dijkstra ​

Tại sao Negative Weights phá vỡ Dijkstra? ​

Lazy Deletion vs Decrease-Key ​

Visualizer States — Dijkstra ​

Sai lầm điển hình — Tránh ngay! ​

Practice ​

🧠 Quiz — BFS Order ​

🧠 Quiz — Dijkstra ​

🐛 Spot the Bug — Dijkstra thiếu lazy deletion ​

Dijkstra bị lỗi — Python ​

🧩 Parsons Problem — Sắp xếp code BFS ​

Sắp xếp đúng thứ tự các dòng code BFS ​

Tổng kết — So sánh 3 thuật toán ​

Duyệt đồ thị — BFS, DFS & Dijkstra

Bức tranh tư duy — 3 cách khám phá mê cung

Graph mẫu — dùng xuyên suốt bài

BFS — Breadth-First Search

Cơ chế hoạt động

ASCII Trace — BFS từ A

Code — BFS

BFS tìm shortest path (unweighted)

Ứng dụng thực tế của BFS

Visualizer States — BFS

DFS — Depth-First Search

Cơ chế hoạt động

ASCII Trace — DFS từ A (iterative)

Code — DFS Recursive

Code — DFS Iterative (an toàn hơn cho graph lớn)

Ứng dụng thực tế của DFS

Visualizer States — DFS

BFS vs DFS — Bảng so sánh quyết định

Dijkstra — Đúng tư duy Priority Queue

Core Idea

Full ASCII Trace — Dijkstra từ A

Code — Dijkstra

Tại sao Negative Weights phá vỡ Dijkstra?

Lazy Deletion vs Decrease-Key

Visualizer States — Dijkstra

Sai lầm điển hình — Tránh ngay!

Practice

🧠 Quiz — BFS Order

🧠 Quiz — Dijkstra

🐛 Spot the Bug — Dijkstra thiếu lazy deletion

Dijkstra bị lỗi — Python

🧩 Parsons Problem — Sắp xếp code BFS

Sắp xếp đúng thứ tự các dòng code BFS

Tổng kết — So sánh 3 thuật toán