Graph Representation
পরিচিতি
গ্রাফ হলো একটি গাণিতিক গঠন যা কিছু বিন্দু (নোড বা ভেরটেক্স) এবং তাদের মধ্যে সংযোগ (এজ) নিয়ে গঠিত। গ্রাফের মাধ্যমে বিভিন্ন সমস্যা মডেল করা যায়, যেমন নেটওয়ার্কের সমস্যা, সড়ক নেটওয়ার্ক, সামাজিক সম্পর্ক ইত্যাদি।
A graph , g = (V , E)
V = vertex
E = Edge (Path)
গ্রাফের প্রকারভেদ
গ্রাফ সাধারণত দুইটি প্রকারে ভাগ করা হয়:
অরিয়েন্টেড গ্রাফ (Directed Graph):
- এখানে এজের একটি নির্দিষ্ট দিক থাকে। অর্থাৎ, A থেকে B যাওয়া একটি এজ কিন্তু B থেকে A যাওয়া হয় না।
আনডিরেক্টেড গ্রাফ (Undirected Graph):
- এখানে এজের কোন দিক নেই। অর্থাৎ, A থেকে B যাওয়ার সাথে সাথে B থেকে A যাওয়া সম্ভব।
গ্রাফের উপস্থাপন পদ্ধতি
গ্রাফের উপস্থাপন করার জন্য প্রধানত দুইটি পদ্ধতি ব্যবহৃত হয়:
অ্যাডজেন্সি ম্যাট্রিক্স (Adjacency Matrix):
- এটি একটি দ্বিমাত্রিক অ্যারে যেখানে সারি এবং কলাম উভয়ই গ্রাফের নোডগুলি নির্দেশ করে।
- যদি দুটি নোডের মধ্যে এজ থাকে, তবে তাদের সংশ্লিষ্ট অবস্থানে ১ এবং না থাকলে ০ থাকবে।
A B C
A 0 1 1
B 1 0 0
C 1 0 0
The matrix is A[n][n] , n = number of vertex .
if (a[i][j] == 1) means i and j are Adjacent
otherwise , a[i][j] == 0
অ্যাডজেন্সি লিস্ট (Adjacency List):
- এটি একটি লিস্টের আকারে, যেখানে প্রতিটি নোডের জন্য তার সাথে যুক্ত নোডগুলির একটি লিস্ট থাকে।
A : B, C
B : A
C : A