মডিউল ১_১ঃ গ্রাফের বেসিক

ট্রি VS গ্রাফ

ট্রি	গ্রাফ
ট্রিতে multiple edge থাকে নাহ।	গ্রাফে multiple edge থাকে।
ট্রিতে multiple way থাকে নাহ। অর্থাৎ একটি নোড থেকে আরেকটি নোডে যেতে শুধুমাত্র একটি way থাকে। এইখানে A নোড থেকে E নোডে যেতে শুধুমাত্র A->B->E এই পথটি দিয়ে যাওয়া যাবে।	গ্রাফে multiple way থাকে । অর্থাৎ একটি নোড থেকে আরেকটি নোডে যেতে এক বা একাধিক way থাকে। এইখানে A নোড থেকে C নোডে যেতে A->B->D->C এবং A->C এই ২টি পথ আছে।
ট্রিতে Cycle পাওয়া যায় নাহ।	গ্রাফে Cycle পাওয়া যায়।
ট্রিতে edge direction শুধু একমুখী হয়, অর্থাৎ edge diraction টি parent থেকে child এর দিকে হয়ে থাকে। উপরে parent নোড A থেকে child নোড B, C দিকে edge গুলোর direction রয়েছে।	গ্রাফে edge direction একমুখী ও উভয়মুখী এই দুই ধরনের হতে পারে। উপরে A নোড থেকে B নোডের দিকে edge direction টি উভয়মুখী , অর্থাৎ A নোড থেকে B নোডে যাওয়া যাবে এবং B নোড থেকে A নোডে যাওয়া যাবে।

গ্রাফের টাইপগুলো

টাইপগুলো	উদাহরণ
Undirected Graph উদাহরণে দেয়া গ্রাফটির edge গুলোর মধ্যে কোন direction নাই, এইটি একটি undirected Graph। এইখানে edge গুলোর মধ্যে connection টি উভয়মুখী , অর্থাৎ A নোড থেকে B নোডে যাওয়া যাবে এবং B নোড থেকে A নোডে যাওয়া যাবে।
Directed Graph উদাহরণে দেয়া গ্রাফটির edge গুলোর মধ্যে direction আছে, তাই সেইটি একটি Directed Graph। এইখানে A নোড থেকে C নোডে যাওয়া যাবে কিন্তু C নোড থেকে A নোডে যাওয়া যাবে নাহ, যেহেতু A নোড থেকে C নোডের edge direction দেয়া আছে A->C ।
Weighted Graph Weighted graph এ দুইট নোডের edge এর মধ্যে cost দেয়া থাকে , এখানে cost বলতে ( সময় , টাকা, সম্পদ ) যেকোনো কিছু হতে পারে।
Unweighted Graph Unweighted graph এ দুইট নোডের edge এর মধ্যে cost দেয়া থাকে না। তাই আমরা প্রতিটি edge এর cost Unweighted graph এ একই ধরে নিতে পারি।
Cycle ( undirected graph) Undirected graph দিয়ে Cycle বানাতে হলে অবশ্যই ৩টি নোডের প্রয়োজন হয়। Cycle ( directed graph) Directed graph এর মধ্যে একে অপরে সাথে edge থাকলেই cycle হবে এমন না, edge গুলোর direction এর উপর নির্ভর করে cycle হবে কিনা। উদাহরণে দেয়া ২য় গ্রাফটি direct graph যেইটিতে cycle পাওয়া যাচ্ছে। A->C->B->A এইভাবে A নোড থেকে C নোড , এরপর C নোড থেকে D নোড, এরপর D নোড থেকে A নোডে যাওয়া যাবে। একটি নোড থেকে যাত্রা শুরু করে আবার সেই নোডটিতে ফিরে আসা যাচ্ছে, তাই গ্রাফটিতে cycle আছে। উদাহরণে দেয়া ৩য় গ্রাফটি direct graph যেইটিতে cycle পাওয়া যাচ্ছে না। কারণ এই গ্রাফটিতে একটি নোড থেকে যাত্রা শুরু করে আবার সেই নোডটিতে ফিরে আসা যাচ্ছে না।	Cycle ( undirected graph) Cycle ( directed graph) No Cycle ( directed graph)