Graph অ্যালগরিদম: BFS, DFS, Dijkstra ও MST

BFS বনাম DFS

Adjacency List ব্যবহার করলে দুটি অ্যালগরিদমেরই Time Complexity O(V + E) এবং Adjacency Matrix ব্যবহার করলে O(V²)।

• BFS (Breadth-First Search): Queue (FIFO) ব্যবহার করে স্তরভিত্তিক (level-by-level) ভিজিট করে এবং Unweighted গ্রাফে সোর্স থেকে প্রতিটি নোডের shortest path নিশ্চিত করে।
• DFS (Depth-First Search): Stack (LIFO) বা Recursion ব্যবহার করে গভীরতায় যায়; Cycle detection, Topological sorting, Strongly Connected Components (SCC) ও Articulation point নির্ণয়ে ব্যবহৃত হয়।

Shortest Path অ্যালগরিদম

• Dijkstra's Algorithm (Greedy): কেবল অঋণাত্মক (non-negative) ওজনের গ্রাফে কাজ করে। Binary Min-Heap সহ জটিলতা O((V + E) log V)। Negative weight edge থাকলে সঠিক ফলাফল নিশ্চিত করতে পারে না।
• Bellman-Ford Algorithm (Dynamic Programming): Negative weight edge থাকলেও কাজ করে এবং Negative weight cycle শনাক্ত করতে পারে। মোট V − 1 বার সব এজ relax করে; সময় জটিলতা O(V · E)।
• Floyd-Warshall Algorithm (Dynamic Programming): All-pairs shortest path বের করে; সময় জটিলতা O(V³) এবং স্পেস O(V²)।

Minimum Spanning Tree (MST)

একটি সংযুক্ত, undirected, weighted গ্রাফের সবগুলো নোডকে (V টি) সর্বনিম্ন মোট ওজনে সংযুক্ত করতে ঠিক V − 1 টি edge লাগে এবং কোনো cycle থাকে না।

• Kruskal's Algorithm: সবগুলো edge ওজন অনুসারে ছোট থেকে বড় সাজিয়ে Disjoint Set Union (DSU) দিয়ে cycle পরীক্ষা করে যোগ করে। সময়: O(E log E) বা O(E log V)। Sparse graph-এর জন্য উপযোগী।
• Prim's Algorithm: একটি নোড থেকে শুরু করে সংযুক্ত সর্বনিম্ন ওজনের edge বেছে ট্রি বড় করে। সময়: O((V + E) log V)। Dense graph-এর জন্য উপযোগী।