လွယ်လွယ်ပြောရရင် Graph ဆိုတာ ဒေတာတွေကို အစက်လေးတွေ (Node) နဲ့ အဲဒီအစက်တွေကို ဆက်ထားတဲ့ မျဉ်း (Edge) တွေနဲ့ ဖော်ပြတဲ့နည်းပါ။ တစ်ခုနဲ့တစ်ခု ဘယ်လို ဆက်စပ်နေလဲဆိုတာကို ပုံဖော်ပြတဲ့နည်းပေါ့။
ကျွန်တော် ဒါကို Facebook သူငယ်ချင်း ပိုက်ကွန်နဲ့ ဥပမာပေးချင်တယ်။ သင်က အစက်တစ်စက်ပါ။ သင့်သူငယ်ချင်းတစ်ယောက်ချင်းစီကလည်း အစက်တစ်စက်စီပါ။ သင်နဲ့ သူငယ်ချင်း ဖြစ်နေတယ်ဆိုတာက မျဉ်းတစ်ကြောင်းပေါ့။ သင့်သူငယ်ချင်းရဲ့ သူငယ်ချင်းကလည်း အဲဒီပိုက်ကွန်ထဲမှာ ပါမယ်။ ဒီလိုနဲ့ လူတွေ အားလုံး ချိတ်ဆက်ထားတဲ့ ပိုက်ကွန်ကြီး ဖြစ်လာတာပါ။ ဒါက Graph အတိုင်းပါပဲ။
Google Maps ကိုလည်း စဉ်းစားကြည့်ပါ။ လမ်းဆုံတစ်ခုချင်းစီက Node ပါ။ လမ်းဆုံနှစ်ခုကြားက လမ်းက Edge ပါ။ Google Maps က သင့်ကို အတိုဆုံးလမ်း ရှာပေးနိုင်တာက ဒီ Graph ကို တွက်ချက်လို့ပါ။ Node တွေ၊ Edge တွေ များလာလေလေ Graph က ကြီးလာလေလေ ဖြစ်ပါတယ်။
Graph က ဘယ်လို အမျိုးအစားတွေ ရှိလဲ?
Graph ကို အဓိက ၂ မျိုး ခွဲလို့ ရပါတယ်။
Undirected Graph — မျဉ်းက နှစ်ဖက်သွားလို့ ရတဲ့ ပုံစံပါ။ Facebook သူငယ်ချင်းလိုပေါ့။ သင်က သူ့သူငယ်ချင်းဆိုရင် သူကလည်း သင့်သူငယ်ချင်း ဖြစ်တာပါ။ မျဉ်းက နှစ်ဖက်လုံး သွားလို့ ရပါတယ်။
Directed Graph — မျဉ်းက တစ်ဖက်တည်းပဲ သွားလို့ ရတဲ့ ပုံစံပါ။ Instagram Follow လိုပေါ့။ သင်က တစ်ယောက်ကို Follow လုပ်တယ်ဆိုတိုင်း သူက သင့်ကို ပြန် Follow မလုပ်ပါဘူး။ မျဉ်းမှာ မြှားပါပြီး တစ်ဖက်တည်း သွားတာပါ။
နောက်တစ်မျိုး ရှိသေးတယ်။ Weighted Graph လို့ ခေါ်ပါတယ်။ Edge တစ်ခုချင်းစီမှာ အလေးချိန် (Weight) ပါတာပါ။ ဥပမာ Google Maps မှာ လမ်းတစ်လမ်းက ၅ ကီလိုမီတာ၊ နောက်တစ်လမ်းက ၁၀ ကီလိုမီတာ ဆိုရင် အဲဒီကီလိုမီတာ အရေအတွက်က Weight ပါ။ AI က အတိုဆုံးလမ်း ရှာတဲ့အခါ Weight ကို ကြည့်ပြီး ဆုံးဖြတ်ပါတယ်။
Graph ကို ဘယ်နေရာတွေမှာ သုံးလဲ?
လမ်းရှာတာ — Google Maps, Grab တို့လို App တွေက လမ်းဆုံတွေကို Graph အဖြစ် မှတ်ပြီး အတိုဆုံးလမ်း၊ အမြန်ဆုံးလမ်းကို ရှာပေးပါတယ်။ ဒါကို Dijkstra’s Algorithm လို့ ခေါ်ပါတယ်။
သူငယ်ချင်း အကြံပေးတာ — Facebook က “သင် သိချင်ကောင်းသိမယ့်သူ” လို့ ပြတာက Graph ကို သုံးတာပါ။ သင့်သူငယ်ချင်းရဲ့ သူငယ်ချင်းတွေထဲက သင်နဲ့ အဆက်များတဲ့သူကို ရှာပေးတာပါ။
YouTube, Netflix အကြံပေးတာ — ကြည့်ဖူးတဲ့ Video တွေ၊ သီချင်းတွေကို Node အဖြစ် မှတ်ပြီး ဆက်စပ်မှုရှိတာတွေကို ရှာပေးပါတယ်။
လေယာဉ် ခရီးစဉ် — လေဆိပ်တစ်ခုချင်းစီက Node၊ လေယာဉ်ပျံသန်းတဲ့ လမ်းကြောင်းက Edge ပါ။ ဘန်ကောက်ကနေ ရန်ကုန်ကို အတိုဆုံးလမ်း ရှာတာလည်း Graph ပါပဲ။
Computer Network — ကွန်ပျူတာတွေကို ချိတ်ဆက်ထားတဲ့ Network ကိုယ်တိုင်က Graph တစ်ခုပါ။ Internet က Router တွေကြား Data ဘယ်လမ်းက သွားရမလဲ ဆုံးဖြတ်တာလည်း Graph နဲ့ပါ။
Graph ကို ဘယ်လို လျှောက်လှမ်းလဲ?
Graph ထဲမှာ တစ်ခုခု ရှာချင်ရင် နည်းလမ်း ၂ ခု ရှိပါတယ်။
BFS (Breadth-First Search) — အနီးအနားက အစက်တွေကို အရင် စစ်တဲ့နည်းပါ။ ရေထဲကို ကျောက်ခဲပစ်လိုက်ရင် လှိုင်းက အဝိုင်းလိုက် ပျံ့သွားသလိုပေါ့။ အနီးဆုံးကနေ အဝေးကို တစ်ဆင့်ချင်း ရှာသွားတာပါ။ အတိုဆုံးလမ်း ရှာဖို့ အကောင်းဆုံးနည်းပါ။
DFS (Depth-First Search) — လမ်းတစ်လမ်းကို အဆုံးထိ လျှောက်သွားတဲ့နည်းပါ။ လမ်းခွဲတစ်ခုမှာ တစ်ဖက်ကို ရွေးပြီး အဆုံးထိ သွားတယ်။ မတွေ့ရင် နောက်တစ်ဖက်ကို ပြန်လျှောက်တယ်။ Maze ထဲက ထွက်ပေါက် ရှာသလိုပေါ့။
Python မှာ Graph ကို အလွယ်တကူ ရေးလို့ ရပါတယ်။ Dictionary နဲ့ပေါ့။
graph = {
"Yangon": ["Mandalay", "Naypyitaw"],
"Mandalay": ["Yangon", "Pyin Oo Lwin"],
"Naypyitaw": ["Yangon"],
"Pyin Oo Lwin": ["Mandalay"]
}
ဒီမှာ မြို့တစ်မြို့ချင်းစီက Node ပါ။ List ထဲက မြို့တွေက အဲဒီမြို့နဲ့ တိုက်ရိုက်ဆက်နေတဲ့ မြို့တွေပါ။ ဒီလောက်လေးနဲ့ Graph တစ်ခု ဖြစ်သွားပါပြီ။
Tree နဲ့ ဘာကွာလဲ?
Tree ဆိုတာ Graph ရဲ့ အထူးပုံစံတစ်မျိုးပါ။ Tree မှာ လမ်းကြောင်း တစ်ခုတည်းပဲ ရှိပြီး၊ စက်ဝိုင်း (Cycle) မရှိပါဘူး။ ဥပမာ ကိုယ့်ဖိုင်စနစ် (File System) က Tree ပါ။ Folder တစ်ခုထဲကနေ နောက် Folder တစ်ခုကို သွားဖို့ လမ်းတစ်လမ်းပဲ ရှိပါတယ်။ Graph ကတော့ ပိုလွတ်လပ်ပါတယ်။ Node နှစ်ခုကြားမှာ လမ်းကြောင်းများစွာ ရှိနိုင်ပြီး၊ စက်ဝိုင်းလည်း ဖြစ်နိုင်ပါတယ်။ Facebook သူငယ်ချင်း ပိုက်ကွန်မှာ A က B ကို သိတယ်၊ B က C ကို သိတယ်၊ C က A ကိုပါ ပြန်သိတယ်ဆိုရင် အဲဒါ စက်ဝိုင်းဖြစ်နေတာပါ။ Tree မှာတော့ ဒီလို မဖြစ်နိုင်ပါဘူး။
ကျွန်တော် Code ရေးစတုန်းက Graph ဆိုတာ နားလည်ရခက်တယ်လို့ ထင်ခဲ့တယ်။ တကယ်တော့ ကိုယ်နေ့တိုင်း သုံးနေတဲ့ ပိုက်ကွန်တွေပဲ ဖြစ်နေတာပါ။ သူငယ်ချင်း ပိုက်ကွန်၊ လမ်းမြေပုံ၊ လေယာဉ်လမ်းကြောင်း — ဒါတွေအားလုံး Graph တွေပါ။ Graph ကို နားလည်သွားရင် Google Maps က ဘာလို့ လမ်းတိုကို ရှာပေးနိုင်တာလဲ၊ Facebook က ဘာလို့ ကိုယ့်သူငယ်ချင်းကို သိနေတာလဲ ဆိုတာ အလိုလို သဘောပေါက်သွားပါလိမ့်မယ်။ 🙂
—
