DFS এবং BFS গ্রাফ ট্রাভার্সাল টেকনিকস

গ্রাফ ট্রাভার্সাল টেকনিক্স (Graph Traversal Techniques) গ্রাফের সকল নোড বা কোণাগুলি এক্সপ্লোর করতে ব্যবহৃত হয়। DFS (Depth-First Search) এবং BFS (Breadth-First Search) হল সবচেয়ে প্রচলিত এবং গুরুত্বপূর্ণ গ্রাফ ট্রাভার্সাল টেকনিক্স। প্রতিটি টেকনিক গ্রাফে বিভিন্ন উদ্দেশ্যে ব্যবহৃত হয়, যেমন সলিউশন খোঁজা, পাথ খোঁজা, অথবা কমপ্লেক্স ডেটা স্ট্রাকচার অনুসন্ধান।

1. Depth-First Search (DFS)

DFS একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি নির্দিষ্ট নোড থেকে শুরু করে যতক্ষণ না সম্ভব হয়, সেই নোডের সমস্ত প্রতিবেশী বা সংযুক্ত নোডগুলোকে একের পর এক এক্সপ্লোর করতে থাকে। এটি সাধারণত stack ডেটা স্ট্রাকচার ব্যবহার করে কাজ করে।

DFS এর কাজের পদ্ধতি:

1. একটি স্টার্টিং নোড নির্বাচন করা হয়।
2. স্টার্টিং নোডটি পরিদর্শন করা হয় এবং তাকে "ভিজিটেড" হিসেবে চিহ্নিত করা হয়।
3. প্রতিটি adjacent (প্রতিবেশী) নোড পরিদর্শন করার জন্য DFS পুনরায় নিজেকে কল করে (রিকার্সিভভাবে)।
4. যদি একটি নোডে কোনও অবশিষ্ট প্রতিবেশী নোড না থাকে, তাহলে সেই নোড থেকে ব্যাকট্র্যাক করা হয় এবং পূর্ববর্তী নোডে ফিরে যাওয়া হয়, যেখানে অবশিষ্ট প্রতিবেশী নোড থাকতে পারে।

DFS এর প্রয়োগ:

• ব্যাকট্র্যাকিং সমস্যা সমাধানে (যেমন: সুইট অ্যালগরিদম, মেজরের সমস্যাগুলির জন্য)।
• টপোলজিক্যাল সোর্টিং এবং বিপজ্জনক সাইকেল শনাক্তকরণ।

DFS এর উদাহরণ:
ধরা যাক, একটি গ্রাফ নিচের মত আছে:

   A
  / \
 B   C
 |   |
 D---E

প্রথমে A থেকে শুরু করলে, DFS এর মাধ্যমে ট্রাভার্সাল হবে: A → B → D → E → C (stack ব্যাকট্র্যাকিংয়ের মাধ্যমে ধীরে ধীরে প্রতিটি নোডে ফিরে আসবে)।

প্রোলগে DFS এর কোড উদাহরণ:

% DFS traversal in Prolog
dfs(Node, Visited) :- 
    \+ member(Node, Visited),  % Check if node is already visited
    write(Node), nl,            % Print the node
    dfs_neighbors(Node, [Node|Visited]). % Call dfs for neighbors

dfs_neighbors(Node, Visited) :- 
    adjacent(Node, Neighbor),   % Find adjacent neighbors
    dfs(Neighbor, Visited).      % Recursively traverse

adjacent(a, b).
adjacent(a, c).
adjacent(b, d).
adjacent(c, e).
adjacent(d, e).

2. Breadth-First Search (BFS)

BFS হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যেখানে প্রথমে start node থেকে শুরু করা হয় এবং তার সমস্ত প্রতিবেশী নোড পরিদর্শন করার পর, তাদের প্রতিবেশী নোডগুলোকে পরবর্তীতে একে একে পরিদর্শন করা হয়। এটি queue ডেটা স্ট্রাকচার ব্যবহার করে কাজ করে, যা FIFO (First In First Out) পদ্ধতিতে কাজ করে।

BFS এর কাজের পদ্ধতি:

1. একটি স্টার্টিং নোড নির্বাচন করা হয়।
2. স্টার্টিং নোডটি queue এ যোগ করা হয় এবং পরবর্তীতে পরিদর্শন করা হয়।
3. যখন queue এ একটি নোড আছে, তখন সেই নোডটি dequeue করা হয় এবং তার প্রতিবেশী নোডগুলোকে queue এ যোগ করা হয়।
4. এভাবে, level-wise বা layer by layer পরিদর্শন করা হয় এবং যখন কোনো নোডের সব প্রতিবেশী পরিদর্শন হয়ে যায়, তখন তার পরবর্তী নোডের দিকে এগিয়ে যায়।

BFS এর প্রয়োগ:

• Shortest path খুঁজে বের করতে (যেমন: সার্চ গেমস বা শত্রু অবস্থান অনুসন্ধান)।
• বিপজ্জনক সাইকেল শনাক্তকরণ এবং লেভেল অনুযায়ী তথ্য সংগ্রহ।

BFS এর উদাহরণ:
ধরা যাক, একটি গ্রাফ নিচের মত আছে:

   A
  / \
 B   C
 |   |
 D---E

এখানে A থেকে শুরু করে, BFS ট্রাভার্সাল হবে: A → B → C → D → E (level-wise ট্রাভার্সাল হবে)।

প্রোলগে BFS এর কোড উদাহরণ:

% BFS traversal in Prolog
bfs(Start) :- bfs([Start], []).

bfs([], _).
bfs([Node|Rest], Visited) :-
    \+ member(Node, Visited),   % Check if node is already visited
    write(Node), nl,             % Print the node
    findall(Neighbor, adjacent(Node, Neighbor), Neighbors),  % Find all neighbors
    append(Rest, Neighbors, Queue),  % Append neighbors to the queue
    bfs(Queue, [Node|Visited]).   % Recursively traverse

adjacent(a, b).
adjacent(a, c).
adjacent(b, d).
adjacent(c, e).
adjacent(d, e).

DFS এবং BFS এর তুলনা

সারসংক্ষেপ:

• DFS (Depth-First Search) একে একে একটি গহীন পদ্ধতিতে গ্রাফের নোডগুলি পরিদর্শন করে এবং stack ব্যবহার করে।
• BFS (Breadth-First Search) স্তরের মাধ্যমে (level by level) গ্রাফের নোডগুলি পরিদর্শন করে এবং queue ব্যবহার করে।
• DFS সাধারণত বেশি মেমরি দক্ষ, তবে লম্বা বা জটিল গ্রাফে ব্যাকট্র্যাকিং প্রয়োজন হতে পারে।
• BFS সাধারণত দ্রুততম পাথ খুঁজে পায় (shortest path) এবং level-wise সার্চ করতে সাহায্য করে।