ကိုယ်တိုင် Graph နဲ့ပတ်သတ်တဲ့ Leetcode တွေရှင်းတဲ့အချိန်မှာ နဲနဲအခက်အခဲဖြစ်နေလို့ သေချာလိုက်ကြည့်ဖြစ်လို့ မြန်မာလိုရေးထားတာလဲမတွေ့မိလို့ ကိုယ်တိုင်လိုက်လေ့လာရင်းနှင့် တခြားကိုယ့်လိုသိချင်တဲ့သူတွေလဲ မြန်မာလိုလွယ်လွယ်ကူကူဖတ်ပီးနားလည်ပါစေဆိုတဲ့ စိတ်နှင့်ရေးထားတာပါ။ မှားယွှင်းနေတာ လွဲနေတာတွေရှိရင် comment မှာထောက်ပြပေးဖို့ပြောလိုပါတယ်။ ကျနော် reference ယူထားတဲ့ video တွေစာအုပ်တွေကိုအောက်ဆုံးမှာဖော်ပြထားပါတယ်။

ဒီ Graph အကြောင်းကိုမဖတ်ခင်သိထားရမယ့်ဟာလေးတွေရှိပါတယ်။ Basic Data structure နှင့် Recurssion လိုမျိုးပေါ့။ အခြေခံ Data structure တွေအကြောင်းကို ကျနော်ဒီမှာ ဘာသာပြန်ထားတာရှိပါတယ်။

ဒီမှာ ကျနော်ရေးထားတာမြန်မာလိုရေးထားပီးတော့ စကားလုံးတော်တော်များများကို ကျနော်ဘာသာပြန်ဖို့မကြိုးစားထားပါဘူး။ ဘာလို့လဲဆိုရင် ကျနော်တို့ leetcode problem တွေဖြေရှင်းတဲ့အချိန်မှာဘဲဖြစ်ဖြစ် တခြားစာအုပ်တွေဖတ်တဲ့အခါမှာလဲ ဒီစကားလုံးတွေကသုံးနေရမှာမလို့ပါ။ တက်နိုင်သလောက်တော့ ဘာသာပြန်ပီးထည့်ထားပါတယ်။

Graph ဆိုတာဘာလဲ

graph = nodes + edges တွေပေါင်းထားတဲ့ကောင်ပေါ့။

Graph က non-linear data structures။

non-linear မပြောခင် linear ဆိုတာဘာလဲဆိုတာရှင်းရအောင်။ Linear data structure ဆိုတာ arrays တို့ linked lists တို့လို data structure မျိုးကိုခေါ်တာ။ သူတို့မှာ စမှတ်/ဆုံးမှတ်ရှိတယ်။

ဥပမာနှင့် မျက်လုံးထဲမြင်အောင်ပြောရမယ်ဆိုရင်…

Linear data structure ဆိုတာမျိုးက စာအုပ်တအုပ်ကို တရွတ်ချင်း စာမျက်နှာ ၁ ကနေ ၂၊ ၂ ကနေသုံး အဲ့လိုမျိုးကနေနောက်ဆုံးစာအုပ်ပီးတဲ့ထိအစဥ်လိုက်ဖတ်တာမျိုးပေါ့။

Non-linear data structure ဆိုတာက internet မှာ web page တွေကို browsing လုပ်နေသလိုဘဲ၊ ပထမဆုံး website home page မှာအဲ့ home page မှာဘဲ links တွေအများကြီးရှိတယ်၊ ကိုယ်ကြိုက်တဲ့ link ကိုနှိပ်ပီးတော့ တခြား page တွေကိုသွားလို့ရတယ်။ ကိုယ်ရောက်သွားတဲ့ link တွေမှာလဲတခြား link တွေရှိနေနိုင်တာဘဲ။ ပြောချင်တာကဒီမှာက အစီအစဥ်လိုက်မဟုတ်ဘူး direction တွေအများကြီးသွားလို့ရတယ်။ ဒါမျိုးပေါ့။

ဒါဆို nodes ကဘာလဲပေါ့။ လောလောဆယ် Circle ထဲမှာ data ရှိတဲ့ကောင်တွေလို့မှတ်ထားလိုက်မယ်။ Nodes တွေကို vertex ဆိုပီးတော့လဲသုံးကြတယ်။ ကျနော်တော့ဒီမှာ node ဆိုပီးဘဲဆက်သုံးသွားမယ်။

အောက်ကပုံက nodes တွေပေါ့။

ဒါဆို edges ကဘာလဲပေါ့။ Nodes တွေဆက်ထားတဲ့ကောင်ပေါ့။ ဥပမာ a နှင့် c မှာ connection ရှိတယ်ဆိုစို့ ဒါကို formal ပြောရင် a နှင့် c ကြားမှာ edge တခုရှိတယ်ပေါ့။ nodes တွေကြားမှာ edges တွေလိုအပ်ရင်လိုအပ်သလို edges တွေထက်ထည့်လို့တယ်။

ဒီအောက်ကပုံကတော့ Graph ပေါ့။ (ငယ်ငယ်တုန်းကသင်ခဲ့ရတဲ့ X,Y ပါတဲ့ graph မဟုတ်ဘူးဆိုတာမြင်လောက်ပါပီ 😁)။ ဒီလောက်ဆိုရင် graph ဆိုတာဘာလဲအခြေခံသိသွားလောက်ပီထင်ပါတယ်။

ဒီဘေးက graph ပုံကိုကြည့်ပီးတော့ nodes တွေက things တွေဆိုရင် edges တွေက relationships တွေပေါ့။

Graph ၂ မျိုးရှိတယ်။ directed graph နှင့် undirected graph ဆိုပီးတော့။

Directed graph နှင့် Undirected graph ဘာကွာလဲ

မြင်သာအောင်ပြောမယ်ဆိုရင် directed graph ကမျှားပြထားတဲ့အတိုင်းသွားရမယ်။ undirected graph ကသွားချင်သလိုသွားလို့ရမယ်။

directed graph မှာ a ကနေ c ကိုသွားလို့ရမယ်။ ဒါပေမယ့် c ကနေ a ကိုပြန်သွားလို့မရဘူး။ direct လုပ်ထားတဲ့မျှားအတိုင်းဘဲသွားလို့ရမယ်။ (တနည်း one way ဘဲရတယ်)
undirected graph မှာ c မှာရောက်နေတယ်ထားပါတော့။ c ကနေ a ကိုသွားချင်သွားလို့ရသလို c ကနေ e ကိုလဲသွားလို့ရတယ်။ ပြောရရင် two way ရတယ်ပေါ့။

ပြန်ချုပ်ကမယ်ဆိုရင် directed graph ကအပေါ်ကနေအောက်သွားတဲ့နေရာမှာသုံးတယ်။ Undirected ကတော့ ဟိုဘက်ဒီဘက် ၂ way သွားလို့ရတဲ့နေရာမှာသုံးတယ်။

---

လောလောဆယ်တော့ ကျနော်တို့ directed graph ကိုဘဲအဓိကပြောမယ်။

ကျနော်တို့ graph အကြောင်းပြောတဲ့အချိန်မှာအသုံးဝင်တဲ့ term တခုရှိတယ် အဲ့ကောင်ကဘာလဲဆိုရင် neighbour။ ဥပမာ ကျနော်က a မှာဆိုရင် c နှင့် b က a ရဲ့ neighbour တွေပေါ့။

အခုကပုံတွေနဲ့အရင်ဆုံးမြင်သာအောင်ပြနေတာပေါ့။ အဲ့မှာကျနော်တို့ကုဒ်ရေးကြမယ်ဆိုရင် ဒီ graph ကို program နည်းကျကျရေးရမယ်။ ဘယ်လိုရေးမလဲဆိုတာတချက်အောက်မှာကြည့်ကြည့်လိုက်အောင်။

ကျနော်တို့ရေးထားတာရှင်းပါတယ်။ ပထမဆုံး a node ရှိတယ်။ a မှာ b,c neighbour တွေရှိတယ်။ အဲ့တော့ကျနော်တို့အိမ်နီးနားချင်း (ဘေးကပ်ရပ်ရှိနေတဲ့ node) စာရင်းထဲထည့်လိုက်တယ်… English လို adjacency list လို့လဲခေါ်ကြတယ်။ တခုသတိထားရမှာက d မှာဆိုရင်သူ့မှာ neighbour မရှိဘူး။ b,c,d,e,f လဲထိုနည်းအတိုင်းဘဲ၊ တခုချင်းစီတော့မရှင်းတော့ဘူး အပေါ်ကပုံနှင့် တွဲကြည့်ရင်ပိုအဆင်ပြေမယ်။

{
	a: [b, c],
	b: [d],
	c: [e],
	d: [],
	e: [b],
	f: [d]
}

---

ကျနော်တို့ graph အကြောင်းပြောပီဆိုရင် graph ထဲမှာရှိတဲ့ nodes တွေကို စနစ်တကျ systematically node တခုချင်းစီကိုတခါ visit လုပ်တဲ့ algorithm တွေအကြောင်းကိုအရင်လေ့လာကြမယ်။ အဲ့လိုမျိုး algorithm တွေကို Traversal algorithm ဆိုပီးတော့လဲခေါ်တယ်။ ကျနော်တို့က Graph မှာဆိုတော့ Graph Traversal ပေါ့။

Graph Traversal ထဲမှာ popular ဖြစ်တဲ့ traversal algorithm ၂ ခုကကတော့ breadth first algorithm နှင့် depth first algorithm အကြောင်းကိုကျနော်တို့ပြောမယ်။ ဒီနှစ်ခုမှာ ဘာကွာလဲဆိုရင် breadth first က source node ကနေစပီးတော့ သူ့ဘေးက neighbour ကိုသွားတယ်။ သူက Queue data structure ကိုသုံးတယ်။ နည်းနည်းမြင်သွားအောင် အောက်ကပုံကိုတချက်ကြည့်လိုက်ရအောင်

ပုံ၁ ကိုကြည့်မယ်ဆို ကျနော်တို့ a node ကနေစပီးတော့ neighbour တွေကိုသွားတယ်။ ပုံ၂ ကိုကြည့်မယ်ဆိုရင် အဲ့ neighbour တွေရဲ့ neighbour တွေကိုဆက်သွားတယ်… အဲ့လိုမျိုးပေါ့။

Depth-First Algoritham ကကြတော့ source node ကနေစတာဘဲ ဒါပေမယ့်သူကကြတော့ neighbor တွေနဲ့သွားတာမဟုတ်ဘဲ တဖက်ဆိုတဖက်ဆက်သွားနေတာ။ သူ့ကိုကြတော့ stack data structure သုံးပီးတော့ implement လုပ်လို့ရသလို recursively လဲလုပ်လို့ရတယ်။ သူ့ကိုလဲမြင်သာအောင်ပုံလေးနဲ့ တချက်ကြည့်ကြည့်ရအောင်။

ပုံ၁ ကိုကြည့်မယ်ဆိုရင် ကျနော်တို့စတဲ့ node က a node ကနေစမယ်။ အောက်ဘက်ကိုအရင်သွားမယ်လို့ရွေးလိုက်တယ်။ အဲ့တော့ b,d ကိုသွားတယ်။ သူကတဖက်ဆိုတဖက်အရင်သွားတာဖြစ်တဲ့အတွက် a,b,d ကိုသွားတယ် အဲ့ဒါပီးတော့နောက်ထက်တဖက်ဖြစ်တဲ့ a,c ကိုသွားမယ်။

ဒီမှာ nodes နဲနဲလေးတွေနဲ့ဆိုသိပ်ပီးမသိသာပေမယ့် 10×10 square ရှိတဲ့ box ပေါ်မှာ BFS နဲ့ DFS အလုပ်လုပ်ပုံကိုဆွဲရင်သူတို့အလုပ်လုပ်တဲ့ပုံကွာခြားတာကိုသေချာမြင်ရမယ်။ ကိုယ်တိုင်ဆွဲပီးတော့စမ်းကြည့်ကြည့်ပါ။

---

ကျနော်တို့အပေါ်မှာ Depth First Algorithm က Stack data structure ကိုသုံးတယ်၊ Breadth First Algorithm က Queue data structure ကိုသုံးတယ်ဆိုပီးပြောခဲ့တယ်။ ဒီ data structure တွေကိုသိပ်မမှတ်မိရင်မှတ်မိအောင် နည်းနည်းပြန်ရှင်းမယ်။ Stack ဆိုတာက ပုဂံတွေဆေးဖို့ထပ်ထားသလိုဘဲ ထက်ထည့်မယ်ဆိုအပေါ်မှာထက်တင်မယ် ဆေးမယ်ဆိုရင်အပေါ်ဆုံးကကောင်ကိုယူမယ်။ Queue ကတော့ ကော်ဖီဆိုင်မှာကော်ဖီဝယ်ဖို့တန်းစီသလိုဘဲ အရင်ဆုံးလာတဲ့ကောင်ကို အရင်ဆုံးကော်ဖီပေးမယ်။ နောက်မှလာတဲ့ကောင်က နောက်မှာတန်းစီကမယ်။ DFS နှင့် BFS မှာ သူတို့စီတဲ့ပုံစံကွဲတာကိုသတိထားဖို့ပြောတာပါ။

---

Depth First Algorithm ကိုမြင်သာအောင်ပုံနှင့်သေချာရှင်းပြမယ်။ Stack data structure သုံးပီးတော့ traversal ဘယ်လိုလုပ်လဲဆိုတာတခုချင်းစီကြည့်လိုက်ကြရအောင်…

Stack Data structure က Last In, First Out (LIFO) Data Structure ဖြစ်တယ်။ ပုဂံဆေးဖို့ချထားတဲ့ပုံစနှင့်မြင်ကြည့်မယ်ဆိုရင် ပုဂံဆေးဖို့ပထမပုဂံချထားမယ်။ နောက်လူလာရင်အရင်ပုဂံအပေါ်မှာတင်လိုက်မယ်။ ဆေးမယ့်သူကအပေါ်ဆုံးပုဂံကိုယူမယ်။ အဲ့လိုမျိုးမြင်ကြည့်လိုက်ရင်မှတ်မိလွယ်မယ်။

ပထမဆုံးကျနော်တို့ graph တခုရှိမယ်။ Depth First Algorithm နှင့် traversal ဖို့ကျနော်တို့ ပုံ ၁ မှာပြထားသလိုဘဲ a ကိုကျနော်တို့ရွေးလိုက်မယ်။ ပီးရင် stack လုပ်မယ်၊ stack မှာသူတခုဘဲရှိတဲ့အတွက်သူ့ကိုဘဲထုတ်လိုက်ပီးတော့ print လုပ်လိုက်မယ်။

အဲ့တော့ a ရဲ့ neighbor တွေဖြစ်တဲ့ c,b ကိုသွားတယ်။ ပုံ ၂ ကိုကြည့်ရမှာပေါ့။ သူတို့ကို stack ပေါ်တင်လိုက်တယ်။ b ကအပေါ်မှာဖြစ်တဲ့အတွက်သူ့ကိုဆွဲထုတ်ပီးတော့ print လုပ်လိုက်တယ်။ c ကတော့ stack မှာဘဲကျန်နေမယ်။

ပုံ၃ ကိုကြည့်လိုက်ရအောင်၊ b neighbor က d ဖြစ်တဲ့အတွက်သူ့ကို stack လုပ်လိုက်မယ်။ stack ကအပေါ်ဆုံးကနေယူတာဖြစ်တဲ့အတွက် d ကိုဆွဲထုတ်လိုက်မယ် ပီးရင် print လုပ်လိုက်မယ်၊ a,b,d ဆိုပီးရမယ်။

ပုံ၄ ကိုကြည့်မယ်ဆိုရင် d ရဲ့ neighbor က f ဖြစ်တဲ့အတွက်သူ့ကို stack လုပ်လိုက်မယ်။ ထုံးစံအတိုင်းဘဲအပေါ်ဆုံးမှာဖြစ်တဲ့ f ကိုဆွဲထုတ်ပီးတော့ print လိုက်မယ်၊ a,b,d,f ဆိုပီးရမယ်။

ပုံ၅ ကိုကြည့်လိုက်မယ်ဆို f မှာ neighbor မရှိတဲ့အတွက် stack ပေါ်ဘာမှတင်စရာမရှိလိုက်ဘူး။ လက်ရှိ stack ပေါ်မှာရှိနေတဲ့ c ကိုဆွဲတင်ပီး print လိုက်မယ်။

ပုံ၆ ကိုဆက်ကြည့်လိုက်မယ်ဆို ပုံ၅ မှာဆွဲတင်ထုတ်လိုက်တဲ့ c မှာ neighbor ရှိတဲ့အတွက် neighbor e ကို stack ပေါ်တင်လိုက်ပီး stack မှာသူဘဲရှိတဲ့အတွက်ဆွဲတင်ပီးတော့ print လိုက်ပီးတော့ ကျနော်တို့ DFS နည်းနှင့် graph တခုလုံးကို traversal လုပ်နိုင်ခဲ့ပါပီ။

---

Breadth First Algorithm ကိုပုံနှင့်ရှင်းပြပါ့မယ်။ Breadth First က Queue data structure ကိုသုံးတာဖြစ်တဲ့အတွက်တန်းစီသလိုမျိုးဆိုတာကိုမြင်သာအောင် အောက်မှာပုံနှင့်တကွသေချာကြည့်လိုက်ရအောင်…

Queue က “First In, First Out” (FIFO) Data Structure ပါ။ အရင်ဆုံးတန်းစီတဲ့သူက အရင်ဆုံးပစ္စည်းရပီးတော့အရင်ဆုံးထွက်တယ်။ နောက်မှလာတဲ့သူကနောက်မှာတန်းစီရတယ်။

ပုံ၁ ကိုကြည့်မယ်ဆိုရင် ပထမဆုံးကျနော်တို့ a ကနေစမယ်ဆိုပါစို့ Breadth First က Queue data structure ကိုသုံးတဲ့အတွက် တန်းစီနေတဲ့ပုံနှင့်မျှားပြထားတယ်။ အဲ့တော့ a ကသွားတန်းစီတယ်ပေါ့။ ပစ္စည်းရပီးတော့ထွက်သွားတယ် (current)၊ ကျနော်တို့ print ထုတ်လိုက်တယ် a

ပုံ၂ ကိုကြည့်မယ်ဆိုရင် a ရဲ့ neighbour တွေဖြစ်တဲ့ b ကတန်းစီမယ်၊ သူ့နောက်မှာ c၊ b ကပစ္စည်းရသွားမယ်၊ print ထုတ်လိုက်မယ် b

ပုံ၃ ကိုကြည့်မယ်ဆိုရင် b ရဲ့ neighbor ဖြစ်တဲ့ d က c နောက်မှာတန်းစီမယ်၊ c ကပစ္စည်းရသွားမယ်၊ print ထုတ်လိုက်မယ် c

ပုံ၄ ကိုကြည့်မယ်ဆိုရင် c ရဲ့ neighbor ဖြစ်တဲ့ e က d နောက်မှာတန်းစီမယ်၊ d ကပစ္စည်းရသွားမယ်၊ print ထုတ်လိုက်မယ် d

ပုံ၅ ကိုကြည့်မယ်ဆိုရင် d ရဲ့ neighbor ဖြစ်တဲ့ f က နောက်မှာတန်းစီလိုက်မယ်၊ e ကပစ္စည်းရသွားမယ်၊ print ထုတ်လိုက်မယ် e

ပုံ၆ နောက်ဆုံးကိုကြည့်မယ်ဆိုရင် f မှာ neighbor မရှိဘူး၊ သူလဲပစ္စည်းရသွားမယ်။ print ထုတ်လိုက်မယ် f

---

ကျနော်တို့ Depth First နှင့် Breadth First ဘယ်လိုအလုပ်လုပ်လဲဆိုတာကို ပုံနှင့်တကွရှင်းပြထားတဲ့အတွက် သေချာမြင်သွားပီလို့ထင်ပါတယ်။ ကျနော်တို့ code implementation ကိုဆက်သွားပါ့မယ်။

ပထမဆုံးကျနော်တို့ Code နှင့် depthFirstPrint ဆိုတဲ့ function ကို stack data structure ကိုသုံးပီးတော့ implement လုပ်ပါ့မယ်။

const depthFirstPrint = (graph, source) => {
	const stack = [ source ];

	while(stack.length > 0) {
		const current = stack.pop();
		console.log(current)

		for(let neighbor of graph[current]) {
			stack.push(neighbor);
		}
	}
}

const graph = {
	a: ['b', 'c'],
	b: ['d'],
	c: ['e'],
	d: ['f'],
	e: [],
	f: []
}

console.log(depthFirstPrint(graph, 'a')); // acebdf

ဒီ depthFirstPrint ဆိုတဲ့ Function ကို Run လိုက်ရင်ဘယ်လို execute လုပ်သွားလဲဆိုတာကို visual နှင့်ကြည့်ချင်တယ်ဆို ဒီမှာ ကြည့်နိုင်ပါတယ်။

Depth First ကိုဘဲကျနော်တို့ recursive နည်းနဲ့ပါ implement လုပ်လို့ရပါတယ်၊ သူက Stack data structure ကိုသုံးတာကိုး။ အောက်မှာတချက်ကြည့်ကြည့်လိုက်ကြရအောင်။

const depthFirstPrint = (graph, source) => {
    # ပထမဆုံးကျနော်တို့ source ကို print လိုက်မယ်
    console.log(source);
    
    # source မှာ neighbors ရှိတယ်ဆိုရင် သူတို့ကိုတခါ
    # iterate လုပ်ပီးတော့ depthFirstPrint ကိုဘဲပြန်ခေါ်
    for(let neighbor of graph[source]) {
        depthFirstPrint(graph, neighbor);
    }
}


const graph = {
	a: ['b', 'c'],
	b: ['d'],
	c: ['e'],
	d: ['f'],
	e: [],
	f: []
}

console.log(depthFirstPrint(graph, 'a')); // acebdf

---

ကျနော်တို့ breadthFirst implement လုပ်ဖို့ breadthFirstPrint ဆိုတဲ့ function တခု implement လုပ်ကြည့်လိုက်ရအောင်။ breadFirst ကတော့ Queue data structure သုံးတာဖြစ်တဲ့အတွက် recursive နဲ့ implement လုပ်ဖို့အဆင်မပြေဘူးဆိုတာတော့သိထားရပါမယ်။

const breadthFirstPrint = (graph, source) => {
        // queue လုပ်မယ်။
	const queue = [ source ];
        
        // queue နေတဲ့သူရှိလား
	while(queue.length > 0) {
		// စီနေတဲ့သူရှိရင် အဲ့လူကိုလိုချင်တာပေးပီးထုတ်လိုက်မယ်
		const current = queue.shift();
		console.log(current)
                
                // ခုနကစီသွားတဲ့လူရဲ့ neighbours တွေကသွားတန်းစီမယ်
		for(let neighbor of graph[current]) {
			queue.push(neighbor);
		}
	}
}

const graph = {
	a: ['c', 'b'],
	b: ['d'],
	c: ['e'],
	d: ['f'],
	e: [],
	f: []
}

console.log(breadthFirstPrint(graph, 'a')); // acbedf

---