Graph — Representation နှင့် Traversal (BFS vs DFS)

နားလည်ထားရမယ့် အချက်

Graph က relationship network မှန်သမျှကို node နဲ့ edge အနေနဲ့ model လုပ်ပေးတယ် — course တစ်ခုလုံးရဲ့ 'related lessons' link တွေရဲ့ shape အတိအကျပါပဲ။ Standard representation နှစ်မျိုးရှိတယ်။ Adjacency list က node တစ်ခုစီအတွက် ၎င်းနဲ့ တကယ် connect ဖြစ်တဲ့ neighbor ကိုသာ သိမ်းထားတယ် — O(V + E) space ဖြစ်ပြီး graph sparse ဖြစ်တဲ့အခါ efficient ပါတယ် (real-world graph အများစုက sparse ပါ — lesson တစ်ခုက ကျန် lesson အားလုံးနဲ့ related မဖြစ်တတ်ဘူး)။ Adjacency matrix က V×V boolean grid ကို သိမ်းထားတယ် — edge count မရွေး O(V²) space ကုန်ပေမယ့် 'ဒီ node နှစ်ခု connected လား' ဆိုတဲ့ lookup ကို O(1) ပေးတယ်၊ graph dense ဖြစ်နေရင် ဒါမှမဟုတ် ဒီ check ကို ခဏခဏလုပ်ရရင် အသုံးဝင်တယ်။ Traversal order ကတော့ representation နဲ့ ကွဲပြားတဲ့ ရွေးချယ်မှုတစ်ခုပါ။ BFS က queue သုံးပြီး level တစ်ခုချင်းစီ explore လုပ်တယ် — direct neighbor အားလုံးကို neighbor ရဲ့ neighbor ဆီမရောက်ခင် ဦးစွာ visit လုပ်တယ် — ဒါက unweighted graph ထဲမှာ shortest path (edge အနည်းဆုံး) ကို guarantee ပြီးရှာပေးနိုင်တယ်၊ ဘာလို့ဆိုတော့ ပိုနီးတဲ့ node အားလုံးမကုန်ခင် ပိုဝေးတဲ့ node ကို မရောက်နိုင်လို့ပါ။ DFS ကတော့ stack (ဒါမှမဟုတ် recursion) သုံးပြီး path တစ်ခုတည်းအတိုင်း အနက်ဆုံးအထိ ဆင်းသွားပြီးမှ backtrack လုပ်တယ် — deep graph အတွက် memory ပိုသက်သာပြီး reachable node အားလုံး explore လုပ်ဖို့ ဒါမှမဟုတ် cycle detect လုပ်ဖို့ natural ပါ၊ ဒါပေမယ့် shortest-path guarantee ပေးမှာမဟုတ်ဘူး။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ 'related lessons' feature ဟာ graph တစ်ခု အတိအကျပါပဲ — lesson တစ်ခုစီက node ဖြစ်ပြီး၊ topic တူတဲ့၊ တစ်ခုနဲ့တစ်ခု reference လုပ်တဲ့ ဒါမှမဟုတ် prerequisite chain ဖွဲ့တဲ့ lesson တွေကို edge က ချိတ်ပေးတယ်။ Lesson အများစုက catalog တစ်ခုလုံးမဟုတ်ဘဲ handful လောက်ကိုပဲ related ဖြစ်တတ်တာမို့ adjacency list နဲ့ represent လုပ်တာက ကိုက်ညီတယ် — structure ကို sparse ဖြစ်စေပြီး memory light ဖြစ်စေတယ်။ Learner တစ်ယောက်က 'ငါရှိတဲ့နေရာကနေ ဒီ goal lesson ဆီ learning path ရှာချင်တယ်' ဆိုပြီး click နှိပ်တဲ့အခါ edge တွေက initially unweighted ဖြစ်နေတာမို့ ဒီ graph ပေါ်က BFS က related-lesson hop အနည်းဆုံး chain (step အနည်းဆုံး) ကို ရှာပေးတယ်။ DFS ကတော့ graph တူတူပေါ်မှာ task တခြားတစ်ခုအတွက် ပိုကိုက်ညီတယ် — starting point ကနေ reachable lesson အားလုံးကို recursively လျှောက်ပြီး topic map အပြည့်အစုံ တည်ဆောက်တာ ဒါမှမဟုတ် content editor တစ်ယောက် မတော်တဆ ထည့်ထားတဲ့ prerequisite cycle ကို detect လုပ်တာမျိုးပါ။

• Adjacency list က sparse graph အတွက် O(V+E) space နဲ့ efficient၊ adjacency matrix က O(V²) space ဖြစ်ပေမယ့် O(1) edge lookup ပေးတယ်။
• BFS (queue-based) က unweighted graph ထဲ shortest path ကို guarantee ပေးတယ်။
• DFS (stack/recursion-based) က path တစ်ခုတည်းကို အနက်ဆုံးအထိ ဆင်းသွားတယ် — reachability/cycle check လိုတဲ့ task အတွက် ကောင်းတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

from collections import deque

# adjacency list: each lesson lists the lessons it links to as "related"
graph = {
    "python-basics": ["loops", "functions"],
    "loops": ["python-basics", "recursion"],
    "functions": ["python-basics", "recursion"],
    "recursion": ["loops", "functions", "dynamic-programming"],
    "dynamic-programming": ["recursion"],
}

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    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

print(bfs(graph, "python-basics"))

['python-basics', 'loops', 'functions', 'recursion', 'dynamic-programming'] ဟု level-by-level BFS traversal order ကို print ထုတ်မည်။

Wikipedia — Breadth-first search — Data Structures & Algorithms