গ্রাফ (Graphs)
গ্রাফ হল একটি গাণিতিক ডেটা স্ট্রাকচার যা ভেরটেক্স (শীর্ষক) এবং এজ (প্রান্ত) দ্বারা গঠিত। গ্রাফ ব্যবহার করে বিভিন্ন ধরনের সমস্যার মডেলিং করা হয়, যেমন নেটওয়ার্ক, রাস্তা ম্যাপ, সামাজিক নেটওয়ার্ক ইত্যাদি।
গ্রাফের প্রকারভেদ
গ্রাফের বিভিন্ন প্রকার রয়েছে, যার মধ্যে কিছু গুরুত্বপূর্ণ প্রকার নিচে উল্লেখ করা হলো:
১. অর্থোডেক্স গ্রাফ (Undirected Graph): যেখানে প্রান্তের দিক নেই এবং দুটি শীর্ষের মধ্যে একটি সংযোগ থাকে। উদাহরণস্বরূপ, একটি শহরের দুইটি স্থান।
২. দিকনির্দেশিত গ্রাফ (Directed Graph): যেখানে প্রতিটি প্রান্ত একটি নির্দিষ্ট দিক নির্দেশ করে। উদাহরণস্বরূপ, একটি রাস্তার নকশা যেখানে একদিকের ট্রাফিক রয়েছে।
৩. ওজনযুক্ত গ্রাফ (Weighted Graph): যেখানে প্রতিটি প্রান্তের সাথে একটি ওজন যুক্ত থাকে। এটি সাধারণত দূরত্ব বা খরচ নির্দেশ করে।
৪. অসীম গ্রাফ (Cyclic Graph): যেখানে একটি বা একাধিক চক্র থাকে, অর্থাৎ, একটি নোডে ফিরে আসা সম্ভব।
৫. অবসারণকারী গ্রাফ (Acyclic Graph): যেখানে কোন চক্র নেই। যেমন, একটি গাছ (Tree) হল একটি অবসারণকারী গ্রাফ।
৬. বিপরীত গ্রাফ (Complete Graph): যেখানে প্রতিটি শীর্ষের সাথে অন্য সব শীর্ষের সরাসরি সংযোগ থাকে।
BFS (Breadth-First Search)
BFS হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা গ্রাফের সমস্ত শীর্ষগুলোকে স্তরের ভিত্তিতে অনুসন্ধান করে। এটি সাধারণত একটি কিউ (Queue) ব্যবহার করে।
BFS-এর কাজ করার প্রক্রিয়া:
- একটি কিউ তৈরি করুন এবং প্রথম শীর্ষকে এন্ট্রি করুন।
- কিউ থেকে একটি শীর্ষ বের করুন এবং এটি পরিদর্শন করুন।
- পরিদর্শিত শীর্ষের সমস্ত অগ্রবর্তী শীর্ষকে কিউতে এন্ট্রি করুন।
- পুনরাবৃত্তি করুন যতক্ষণ না কিউ ফাঁকা হয়।
উদাহরণ (Python):
from collections import deque
def bfs(graph, start):
visited = set() # পরিদর্শিত শীর্ষের সেট
queue = deque([start]) # কিউতে প্রথম শীর্ষ যুক্ত করা
while queue:
vertex = queue.popleft() # কিউ থেকে শীর্ষ বের করা
if vertex not in visited:
print(vertex) # পরিদর্শন করা
visited.add(vertex) # পরিদর্শিত হিসাবে চিহ্নিত করা
queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited) # অগ্রবর্তী শীর্ষগুলো যুক্ত করা
DFS (Depth-First Search)
DFS হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা গ্রাফের শীর্ষগুলোকে গভীরভাবে অনুসন্ধান করে। এটি সাধারণত একটি স্ট্যাক (Stack) ব্যবহার করে বা রিকারশন (Recursion) মাধ্যমে করা হয়।
DFS-এর কাজ করার প্রক্রিয়া:
- একটি স্ট্যাক তৈরি করুন এবং প্রথম শীর্ষকে এন্ট্রি করুন।
- স্ট্যাক থেকে একটি শীর্ষ বের করুন এবং এটি পরিদর্শন করুন।
- পরিদর্শিত শীর্ষের সমস্ত অগ্রবর্তী শীর্ষকে স্ট্যাকে এন্ট্রি করুন।
- পুনরাবৃত্তি করুন যতক্ষণ না স্ট্যাক ফাঁকা হয়।
উদাহরণ (Python):
def dfs(graph, vertex, visited=None):
if visited is None:
visited = set() # পরিদর্শিত শীর্ষের সেট
if vertex not in visited:
print(vertex) # পরিদর্শন করা
visited.add(vertex) # পরিদর্শিত হিসাবে চিহ্নিত করা
for neighbor in graph[vertex]: # অগ্রবর্তী শীর্ষগুলো
dfs(graph, neighbor, visited) # রিকারশন ব্যবহার করে
উপসংহার
গ্রাফ একটি শক্তিশালী ডেটা স্ট্রাকচার যা বিভিন্ন সমস্যার মডেলিং করতে সক্ষম। গ্রাফের প্রকারভেদ, BFS এবং DFS গ্রাফ ট্রাভার্সাল অ্যালগরিদমের মৌলিক অংশ। BFS স্তরের ভিত্তিতে অনুসন্ধান করে, जबकि DFS গভীরভাবে অনুসন্ধান করে। এগুলি গ্রাফের বিভিন্ন তথ্য বের করার জন্য ব্যবহৃত হয় এবং বিভিন্ন বাস্তব জীবনের সমস্যায় গুরুত্বপূর্ণ ভূমিকা পালন করে।
Read more
