အခန်း ၁၈ - BFS and DFS

အခန်း ၁၇ မှာ graph ကို ကိုယ်စားပြု — adjacency list / matrix ကို လေ့လာခဲ့ပါတယ်။ ပြဿနာ ဖြေတဲ့အခါ — "source ကစ ဆက်နေသမျှ vertex အကုန် ရောက်ကြည့်"၊ "component အုပ်စု ရေတွက်" စတဲ့နေရာတွေမှာ graph ကို လှည့်ပတ်ရှာဖွေ (traverse) ခဲ့ပါတယ်။ ဒီ traversal ၂ မျိုးက — BFS (Breadth-First Search) နဲ့ DFS (Depth-First Search) ပါ။

ဒီနှစ်ခုက graph/tree အလုပ်တိုင်းရဲ့ အခြေခံ ဖြစ်ပါတယ် — ကွာတာက "vertex တွေကို ဘယ်အစဉ် နဲ့ ရှာသွားလဲ" ဆိုတာပဲ —

DFS — လမ်းကြောင်းတစ်ခုကို အဆုံးထိ နက်နက် ဆင်းပြီးမှ နောက်လမ်း ပြန်လှည့် (နက်ရှိုင်းအရင်)။
BFS — start ကနေ အနီးဆုံး အဆင့် vertex တွေ အရင် ၊ ပြီးမှ နောက်အဆင့် (ပတ်လည် တဖြည်းဖြည်း ကျယ်)။

ဒီအခန်းမှာ — DFS/BFS ကို code ထဲ ဘယ်လို ရေးမလဲ၊ ဘယ်အချိန် ဘယ်ဟာ ရွေးမလဲ၊ ပြီးတော့ classic ပြဿနာ ၅ ခု (islands, flood fill, rotten oranges, course schedule, shortest path) ကို ဖြေကြည့်ပါမယ်။

DFS — နက်ရှိုင်းအရင် (Depth-First)

DFS က — vertex တစ်ခုကစ၊ အိမ်နီးချင်းတစ်ခုကို ရွေးပြီး အဲ့လမ်းကို အဆုံးထိ နက်နက် ဆင်းသွားတယ်။ ပိတ်သွားမှ (ဆက်မသွားနိုင်တော့မှ) နောက်ပြန်လှည့် (backtrack) ပြီး မစစ်ရသေးတဲ့ နောက်လမ်းကို ဆက်စစ်တယ်။

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))

DFS အစဉ်: A → B → D (အဆုံး) → backtrack → C

DFS ကို ရေးနည်း ၂ မျိုး ရှိ — recursion (call stack ကို သုံး) နဲ့ explicit stack (ကိုယ်တိုင် stack သုံး)။ နှစ်ခုလုံး က "နောက်ဆုံးရောက် vertex ကို အရင်ဆက်" ဆိုတဲ့ LIFO (stack) သဘောတရားပဲ။

DFS — Recursion

အရိုးရှင်းဆုံး ရေးနည်း — function က သူ့ကိုယ်သူ ပြန်ခေါ်ပြီး၊ programming language ရဲ့ call stack က backtrack ကို အလိုအလျောက် လုပ်ပေးတယ်။

void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;                  // visit မှတ်
    // ... node ကို process လုပ်
    for (int next : graph.get(node)) {
        if (!visited[next]) dfs(graph, next, visited);  // မ visit ရသေးရင် ဆက်ဆင်း
    }
}

DFS — Explicit Stack

Recursion နက်လွန်းရင် stack overflow ဖြစ်နိုင်တယ်။ အဲ့ဒါကို ရှောင်ဖို့ — stack ကို ကိုယ်တိုင်သုံးပြီး iterative ရေးနိုင်တယ်။

void dfs(List<List<Integer>> graph, int start, boolean[] visited) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop(); // နောက်ဆုံးထည့်တာ အရင်ထွက် (LIFO)
        if (visited[node]) continue;
        visited[node] = true; // visit မှတ်
        for (int next : graph.get(node)) {
            if (!visited[next]) stack.push(next);
        }
    }
}

BFS — ပတ်လည်အရင် (Breadth-First)

BFS က — start vertex ကနေ အနီးဆုံး အဆင့် (distance 1) vertex အကုန်ကို အရင်ရှာ၊ ပြီးမှ distance 2 အဆင့်၊ စသဖြင့် တလွှာချင်း ပတ်လည် ကျယ်သွားတယ်။ ဒါကို queue (FIFO) နဲ့ လုပ်တယ် — အရင်ထည့်တဲ့ vertex ကို အရင်ထုတ်ပြီး ဆက်စစ်။

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))

BFS အစဉ်: A → B → C → D (အဆင့်လိုက်)

အဆင့် 0: A
အဆင့် 1: B, C
အဆင့် 2: D

void bfs(List<List<Integer>> graph, int start, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true; // queue ထဲ ထည့်တုန်းကပဲ မှတ်
    while (!queue.isEmpty()) {
        int node = queue.poll(); // အရင်ထည့်တာ အရင်ထွက် (FIFO)
        // ... node ကို process လုပ်
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

သတိ: BFS မှာ vertex ကို queue ထဲ ထည့်တဲ့အချိန်မှာ visited မှတ်ပါ — poll လုပ်တဲ့အချိန် မဟုတ်ပါ။ မဟုတ်ရင် vertex တစ်ခုတည်းကို queue ထဲ အကြိမ်များစွာ ထည့်မိနိုင်တယ်။

Visited Set — Cycle ကာကွယ်ခြင်း

Graph မှာ cycle ရှိနိုင်သည့် အတွက် visit ပြီးသား vertex ကို ပြန်မစစ်အောင် visited set ကို မှတ်ထားဖို့ မဖြစ်မနေ လိုပါတယ်။ မဟုတ်ရင် A → B → A → B ... infinite loop ဖြစ်သွားမယ်။

Tree မှာ cycle မရှိလို့ — visited မလိုဘဲ traverse လို့ ရတယ် (parent ဆီ ပြန်မသွားရင်)။
Graph မှာ — visited မဖြစ်မနေ လို။
Grid (matrix) မှာ — visited array သုံးတာ၊ ဒါမှမဟုတ် cell ကို တန်ဖိုးပြောင်း (ဥပမာ '1' → '0') ၍ "visit ပြီး" ကို မှတ်တာ။

ဘယ်အချိန် BFS, ဘယ်အချိန် DFS

နှစ်ခုလုံး vertex အကုန် ရောက်တာ တူပေမယ့် — ရှာသွားတဲ့ အစဉ် ကွာသည့် အတွက် ပြဿနာ အလိုက် ရွေးချယ်ရတယ်။

	BFS	DFS
Structure	Queue (FIFO)	Stack / Recursion (LIFO)
ရှာပုံ	အဆင့်လိုက် ပတ်လည်	လမ်းတစ်ခု အဆုံးထိ နက်နက်
Shortest path (unweighted)	✓ ရ (အနီးဆုံး အရင်)	✗ မရ
Memory	အဆင့်တစ်ခုလုံး queue ထဲ (ကျယ်ရင် များ)	လမ်းကြောင်း အနက် (နက်ရင် များ)
သင့်တော်	nearest / level / shortest	path exist / cycle / backtracking

အလွယ်မှတ်:

"အနီးဆုံး / အနည်းဆုံး အဆင့် / shortest path" ဆို → BFS။
"path ရှိလား / အကုန်ရှာ / cycle / backtracking" ဆို → DFS (recursion ရေးရ လွယ်)။

Real-world Examples

Search Dependency Tree — package/task dependency ကို DFS နဲ့ ဆင်းပြီး "ဘယ် package တွေ မှီခိုလဲ" အကုန်ရှာ၊ install order ရှာ။
Find Nearest Item — map/grid မှာ "အနီးဆုံး hospital / ATM" ရှာတာ — BFS (အနီးဆုံး အရင် ရောက်လို့)။
Crawl Linked Pages — web crawler — page တစ်ခုကစ link တွေကို BFS/DFS နဲ့ လိုက်ဖွင့်၊ visited URL set နဲ့ ထပ်မဖွင့်အောင်။
Permission Inheritance — role → permission graph ကို DFS နဲ့ ဆင်းပြီး "user ဒီ permission ရှိလား" inherited အကုန်စစ်။
Social Network — "ဒီ user နဲ့ ဘယ်နှ ဆင့်ကွာလဲ (degrees of separation)" — BFS နဲ့ အဆင့်ရေတွက်။

Questions

Graph/grid ပြဿနာ အများစုက — DFS/BFS template ၂ ခုထဲက တစ်ခုကို လိုက်ဖော်ပြီး visited မှတ်ရုံပါပဲ။ classic ၅ ခု ဖြေကြည့်ရအောင်။

၁။ Number of Islands

'1' (ကုန်း) နဲ့ '0' (ရေ) ပါတဲ့ 2D grid ပေးထားသည်။ island (ဘေးချင်းကပ် ကုန်းအုပ်စု — အပေါ်/အောက်/ဘယ်/ညာ ဆက်နေ) ဘယ်နှ ခု ရှိလဲ ပြန်ပါ။

Example 1:

Input: grid = [
  ["1","1","0","0"],
  ["1","1","0","0"],
  ["0","0","1","0"],
  ["0","0","0","1"]
]
Output: 3
   (ဘယ်အပေါ် အုပ်စု၊ အလယ် 1၊ အောက်ညာ 1 — ၃ ကျွန်း)

ရှင်းလင်းချက်

cell အကုန်ကို loop — '1' တစ်ခု တွေ့ရင် → island အသစ် တစ်ခု စပြီ → count တိုး၊ ပြီးတော့ DFS နဲ့ အဲ့ island နဲ့ ဆက်နေတဲ့ '1' အကုန်ကို '0' ပြောင်းပစ် ("visit ပြီး" မှတ်ခြင်း)။ ဒီနည်းနဲ့ island တစ်ခုစီကို တစ်ခါပဲ ရေတွက်တယ်။ (connected component ရေတွက်တာ — grid version ပါ။)

cell (r,c) loop — '1' ဆို count++ + DFS။
DFS — '1' ကို '0' ပြောင်း၊ ဘေး ၄ ဖက် ဆက်ဆင်း (grid အပြင် မထွက်အောင် စစ်)။

Time Complexity: $O(m \times n)$ - cell တစ်ခုစီ တစ်ခါ။
Space Complexity: $O(m \times n)$ - worst case recursion stack (grid အကုန် '1')။

Java Solution

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {       // island အသစ်
                    count++;
                    dfs(grid, r, c);           // ဆက်နေတဲ့ ကုန်း အကုန် နစ်ပစ်
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != '1') return;      // အပြင်ထွက် / ရေ / visit ပြီး
        grid[r][c] = '0';                      // visit မှတ် (ရေ ပြောင်း)
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}

၂။ Flood Fill

image ကို 2D grid image (cell တစ်ခုစီ = အရောင်) နဲ့ ပေးထားသည်။ start cell (sr, sc) ကစ — တူညီတဲ့ အရောင် ဘေးချင်းကပ် cell အကုန်ကို အရောင်အသစ် color နဲ့ ပြောင်းပါ (paint bucket tool)။

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
   ((1,1) ကစ ဆက်နေတဲ့ 1 အကုန် → 2)

ရှင်းလင်းချက်

start cell ရဲ့ မူရင်းအရောင်ကို မှတ်၊ DFS နဲ့ ဆက်နေတဲ့ တူညီအရောင် cell အကုန်ကို color ပြောင်း။ Number of Islands နဲ့ တူ — "ဆက်နေတဲ့ region" ကို DFS နဲ့ စစ်တာ။ သတိ: အရောင်အသစ်က မူရင်းအရောင်နဲ့ တူရင် — ပြောင်းစရာ မလို (infinite loop ရှောင်)။

start cell ရဲ့ မူရင်းအရောင် old မှတ်၊ old == color ဆို ချက်ချင်း ပြန်။
DFS — old အရောင် cell ကို color ပြောင်း၊ ဘေး ၄ ဖက် ဆက်။

Time Complexity: $O(m \times n)$ ။
Space Complexity: $O(m \times n)$ - recursion stack။

Java Solution

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old != color) dfs(image, sr, sc, old, color);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int old, int color) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length
            || image[r][c] != old) return;     // အပြင် / အရောင်မတူ
        image[r][c] = color;                   // ပြောင်း (visit မှတ် ပါ)
        dfs(image, r + 1, c, old, color);
        dfs(image, r - 1, c, old, color);
        dfs(image, r, c + 1, old, color);
        dfs(image, r, c - 1, old, color);
    }
}

၃။ Rotting Oranges

grid မှာ 0 = ဗလာ၊ 1 = လတ်ဆတ်တဲ့ လိမ္မော်သီး၊ 2 = ပုပ်နေတဲ့ သီး။ မိနစ်တိုင်း — ပုပ်သီး ဘေးချင်းကပ် (၄ ဖက်) လတ်ဆတ်သီးတွေ ပုပ်ကုန်တယ်။ သီးအားလုံး ပုပ်ဖို့ အနည်းဆုံး ဘယ်နှ မိနစ် လိုလဲ ပြန်ပါ။ မဖြစ်နိုင်ရင် -1။

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

ရှင်းလင်းချက်

ဒါက multi-source BFS ပါ — ပုပ်သီး အကုန်လုံး ကို start (queue ထဲ အတူတူ ထည့်) ပြီး — အဆင့်တစ်ဆင့်ချင်း (မိနစ်တစ်ခုချင်း) ပတ်လည် ပျံ့သွားတာ။ BFS က "အဆင့်လိုက် ကျယ်" တာ ဖြစ်လို့ — အဆင့် အရေအတွက် = မိနစ်။ နောက်ဆုံး လတ်ဆတ်သီး ကျန်ရင် -1။

ပုပ်သီး အကုန် queue ထဲ ထည့်၊ လတ်ဆတ်သီး အရေအတွက် fresh ရေ။
BFS — အဆင့်တစ်ခုစီ (minutes++) မှာ — queue ထဲက ပုပ်သီးတွေရဲ့ ဘေး လတ်ဆတ်သီးကို ပုပ်စေ + queue ထဲ ထည့် + fresh--။
ပြီးတော့ fresh == 0 ဆို minutes၊ မဟုတ်ရင် -1။

Time Complexity: $O(m \times n)$ ။
Space Complexity: $O(m \times n)$ - queue။

Java Solution

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Queue<int[]> queue = new LinkedList<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) queue.offer(new int[]{r, c});  // source အကုန်
                else if (grid[r][c] == 1) fresh++;
            }
        if (fresh == 0) return 0;

        int minutes = 0;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!queue.isEmpty() && fresh > 0) {
            minutes++;
            for (int i = queue.size(); i > 0; i--) {   // အဆင့်တစ်ခုလုံး (၁ မိနစ်)
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) continue;
                    grid[nr][nc] = 2;              // ပုပ်စေ
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

၄။ Shortest Path in Binary Matrix

n × n binary grid မှာ 0 = သွားလို့ ရ၊ 1 = ပိတ်။ ဘယ်အပေါ်ထောင့် (0,0) ကနေ ညာအောက်ထောင့် (n-1,n-1) သို့ — ၈ ဖက် (ထောင့်ဖြတ် ပါ) သွားလို့ ရတဲ့ အတိုဆုံး လမ်းကြောင်း ရဲ့ cell အရေအတွက် ပြန်ပါ။ မရှိရင် -1။

Example 1:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
   ((0,0)→(0,1)→(1,2)→(2,2)  လမ်းကြောင်း — cell ၄ ခု)

ရှင်းလင်းချက်

Shortest path (unweighted) ဆို → BFS။ start cell ကစ — အဆင့်လိုက် ပတ်လည် ကျယ်သွားတယ်၊ destination ကို ပထမဆုံး ရောက်တဲ့ အဆင့် က အတိုဆုံး။ ဒီမှာ ၈ ဖက် (ထောင့်ဖြတ် ပါ) ရွေ့လို့ ရတယ်။ DFS မသုံးရတဲ့ အကြောင်း — DFS က "ပထမတွေ့တဲ့ လမ်း" ကို ပြန်တာ၊ အတိုဆုံး မဟုတ်နိုင်။

start (0,0) ပိတ် နေရင် -1။
BFS — cell (r,c,dist) queue ထဲ ထည့်၊ visited မှတ်။
destination ရောက်ရင် dist ပြန်၊ queue ကုန်လည်း မရောက်ရင် -1။

Time Complexity: $O(n^2)$ - cell တစ်ခုစီ တစ်ခါ။
Space Complexity: $O(n^2)$ - queue + visited။

Java Solution

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});       // (r, c, dist)
        grid[0][0] = 1;                        // visit မှတ်

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1], dist = cur[2];
            if (r == n-1 && c == n-1) return dist;   // ပထမဆုံး ရောက် = အတိုဆုံး
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 0) continue;
                grid[nr][nc] = 1;              // visit မှတ် (ထည့်တုန်းက)
                queue.offer(new int[]{nr, nc, dist + 1});
            }
        }
        return -1;
    }
}

၅။ Course Schedule

course numCourses ခု (0..numCourses-1) နဲ့ prerequisite list prerequisites ပေးထားသည် — [a, b] ဆို "course a တက်ဖို့ b အရင်ပြီးရမယ်"။ course အကုန် တက်လို့ ရ/မရ (cycle မရှိ/ရှိ) ပြန်ပါ။

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
   (course 0 အရင်၊ ပြီးမှ 1 — ဖြစ်နိုင်)

graph LR
    C0([0]) --> C1([1])

prerequisite မရှိ → 1 ကို တက်လို့ ရ။ Cycle မရှိ။

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
   (0 ← 1 ← 0  ဝိုင်းပြန် — မဖြစ်နိုင်)

graph LR
    D0([0]) --> D1([1])
    D1 --> D0

0 → 1 → 0 ဝိုင်းပြန် — နှစ်ခုလုံး အချင်းချင်း မှီခို → Cycle ရှိ။

ရှင်းလင်းချက်

ဒါက directed graph မှာ cycle ရှိ/မရှိ စစ်တာ — cycle ရှိရင် course အကုန် ဘယ်တော့မှ မပြီးနိုင်။ ဒီမှာ topological thinking ကို မိတ်ဆက်ပါမယ် — BFS topological sort (Kahn's algorithm) သုံးမယ်။ prerequisite မရှိတဲ့ (in-degree 0) course ကစ တက်၊ တက်ပြီးတိုင်း သူ့ပေါ် မှီခိုတဲ့ course တွေရဲ့ in-degree လျှော့၊ 0 ဖြစ်ရင် queue ထဲ ထည့်။ နောက်ဆုံး တက်ပြီး course အရေအတွက် = numCourses ဆို — cycle မရှိ (true)။

adjacency list + in-degree array ဆောက်။
in-degree 0 course အကုန် queue ထဲ။
BFS — course တစ်ခု ထုတ်တိုင်း taken++၊ neighbor in-degree လျှော့၊ 0 ဆို ထည့်။
taken == numCourses ⇒ true။

Time Complexity: $O(V + E)$ - course + prerequisite။
Space Complexity: $O(V + E)$ 。

Java Solution

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        for (int[] p : prerequisites) {        // b → a  (b အရင်)
            graph.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++)
            if (indegree[i] == 0) queue.offer(i);   // prerequisite မရှိ — အရင်တက်

        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            for (int next : graph.get(course)) {
                if (--indegree[next] == 0) queue.offer(next);
            }
        }
        return taken == numCourses;            // အကုန် တက်နိုင် = cycle မရှိ
    }
}

Topological Sort (dependency order ရှာတာ) နဲ့ Course Schedule II (တက်ရမယ့် အစဉ် ပြန်တာ) ကို အခန်း ၁၉ — Advanced Graph Algorithms မှာ အသေးစိတ် ဆက်လေ့လာပါမယ်။