Minimum Spanning Tree (MST) এবং Shortest Path সমস্যা গুলি গ্রাফ তত্ত্বের দুটি অত্যন্ত গুরুত্বপূর্ণ সমস্যা। এই সমস্যাগুলি বিভিন্ন বাস্তব জীবনের সমস্যার সমাধানে ব্যবহৃত হয়, যেমন নেটওয়ার্ক ডিজাইন, রাস্তা নির্মাণ, এবং ট্রাফিক সিস্টেম।
এই টিউটোরিয়ালে আমরা দুটি গুরুত্বপূর্ণ অ্যালগরিদম:
- Minimum Spanning Tree (MST): Kruskal’s Algorithm এবং Prim’s Algorithm
- Shortest Path Algorithms: Dijkstra’s Algorithm এবং Bellman-Ford Algorithm
এগুলোকে Java দিয়ে কিভাবে বাস্তবায়ন করা হয় তা আলোচনা করব।
1. Minimum Spanning Tree (MST)
একটি Minimum Spanning Tree (MST) হল একটি গ্রাফের একটি সাবগ্রাফ যা সমস্ত ভেরটেক্সকে সংযুক্ত করে এবং এর মোট এজ ওজন সবচেয়ে কম থাকে। দুটি সাধারণ MST অ্যালগরিদম হল Kruskal’s Algorithm এবং Prim’s Algorithm।
1.1 Kruskal’s Algorithm
Kruskal’s Algorithm একটি গ্রীড ভিত্তিক অ্যালগরিদম, যেখানে গ্রাফের সমস্ত এজ গুলিকে বাড়ানো বা যুক্ত করার আগে তাদের ওজন অনুসারে সাজানো হয়। অ্যালগরিদমটি গ্রাফের সকল এজকে একটি পরিসরে সাজায় এবং তাদের একে একে MST তে যুক্ত করে, যতক্ষণ না সমস্ত নোড সংযুক্ত হয়।
Steps:
- সমস্ত এজ গুলিকে ওজন অনুযায়ী সাজানো হয়।
- একটি ইউনিয়ন ফাইন্ড ডাটা স্ট্রাকচার ব্যবহার করে প্রতিটি এজ যুক্ত করা হয় যদি এটি সাইকেল তৈরি না করে।
উদাহরণ: Kruskal’s Algorithm
import java.util.*;
class Edge {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
class Graph {
int V, E;
Edge[] edges;
public Graph(int v, int e) {
V = v;
E = e;
edges = new Edge[e];
}
// Utility function to find set of an element i
int find(int[] parent, int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
// Utility function to do union of two subsets
void union(int[] parent, int[] rank, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
// Function to construct MST using Kruskal's algorithm
void kruskalMST() {
Edge[] result = new Edge[V];
int e = 0; // Index variable for result[]
int i = 0; // Initial index of sorted edges
int[] parent = new int[V];
int[] rank = new int[V];
for (i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
Arrays.sort(edges, Comparator.comparingInt(o -> o.weight));
i = 0;
while (e < V - 1) {
Edge next_edge = edges[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
union(parent, rank, x, y);
}
}
System.out.println("Edges in MST:");
for (int j = 0; j < e; j++) {
System.out.println(result[j].src + " -- " + result[j].dest + " == " + result[j].weight);
}
}
}
public class KruskalAlgorithm {
public static void main(String[] args) {
int V = 4; // Number of vertices
int E = 5; // Number of edges
Graph graph = new Graph(V, E);
graph.edges[0] = new Edge(0, 1, 10);
graph.edges[1] = new Edge(0, 2, 6);
graph.edges[2] = new Edge(0, 3, 5);
graph.edges[3] = new Edge(1, 3, 15);
graph.edges[4] = new Edge(2, 3, 4);
graph.kruskalMST();
}
}
ব্যাখ্যা:
- Union-Find ডাটা স্ট্রাকচার: find() এবং union() ব্যবহার করে সাইকেল চেক করা হয়।
- Kruskal’s Algorithm: সমস্ত এজগুলোকে সজ্জিত করা হয়, তারপর একে একে MST তে যুক্ত করা হয় যদি তা সাইকেল সৃষ্টি না করে।
আউটপুট:
Edges in MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
1.2 Prim’s Algorithm
Prim’s Algorithm গ্রাফের একটি আরম্ভিক ভেরটেক্স থেকে শুরু করে MST তৈরি করতে ব্যবহৃত হয়, যেখানে এটি একটি সর্বনিম্ন ওজনের এজ নির্বাচন করে। এটি একটি গ্রিড ভিত্তিক অ্যালগরিদম, যেখানে একে একে সংলগ্ন নোড এবং এজ যুক্ত করা হয়।
Steps:
- প্রাথমিকভাবে একটি সন্নিবিষ্ট ভেরটেক্স নির্বাচন করুন।
- সন্নিবিষ্ট নোডের সাথেই কম ওজনের এজ সিলেক্ট করুন এবং পরবর্তী নোডে যুক্ত করুন।
উদাহরণ: Prim’s Algorithm
import java.util.*;
class GraphPrim {
private int V;
private LinkedList<Edge> adjList[];
public GraphPrim(int V) {
this.V = V;
adjList = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new LinkedList<>();
}
}
static class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
public void addEdge(int src, int dest, int weight) {
adjList[src].add(new Edge(dest, weight));
adjList[dest].add(new Edge(src, weight)); // Undirected graph
}
public void primMST() {
boolean[] visited = new boolean[V];
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
// Start with vertex 0
pq.add(new Edge(0, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int node = edge.dest;
if (!visited[node]) {
visited[node] = true;
System.out.println("Include vertex " + node + " in MST");
for (Edge neighbor : adjList[node]) {
if (!visited[neighbor.dest]) {
pq.add(neighbor);
}
}
}
}
}
}
public class PrimAlgorithm {
public static void main(String[] args) {
GraphPrim graph = new GraphPrim(5);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 3, 6);
graph.addEdge(1, 2, 3);
graph.addEdge(1, 3, 8);
graph.addEdge(2, 3, 1);
graph.addEdge(3, 4, 4);
graph.primMST();
}
}
ব্যাখ্যা:
- Priority Queue ব্যবহার করে, MST এ প্রতিটি নোডের কম ওজনের এজকে সিলেক্ট করা হয়।
- Prim’s Algorithm একটি কনিষ্ঠ সন্নিবদ্ধ এলিমেন্ট যুক্ত করে MST তৈরি করে।
আউটপুট:
Include vertex 0 in MST
Include vertex 1 in MST
Include vertex 2 in MST
Include vertex 3 in MST
Include vertex 4 in MST
2. Shortest Path Algorithms
গ্রাফে সবচেয়ে কম খরচে (কম পাথের ওজন) একটি নির্দিষ্ট নোড থেকে অন্য নোডে পৌঁছানোর জন্য Shortest Path অ্যালগরিদম ব্যবহৃত হয়। দুটি জনপ্রিয় Shortest Path অ্যালগরিদম হল Dijkstra’s Algorithm এবং Bellman-Ford Algorithm।
2.1 Dijkstra’s Algorithm
Dijkstra's Algorithm একটি গ্রাফে একক সোর্স থেকে সকল গন্তব্যের মধ্যে সবচেয়ে ছোট পাথ খুঁজে বের করার জন্য ব্যবহৃত হয়।
উদাহরণ: Dijkstra’s Algorithm
import java.util.*;
public class DijkstraAlgorithm {
private int V;
private LinkedList<Edge> adjList[];
public DijkstraAlgorithm(int V) {
this.V = V;
adjList = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new LinkedList<>();
}
}
static class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
public void addEdge(int src, int dest, int weight) {
adjList[src].add(new Edge(dest, weight));
}
public void dijkstra(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
pq.add(new Edge(src, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int u = edge.dest;
for (Edge e : adjList[u]) {
int v = e.dest;
int weight = e.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new Edge(v, dist[v]));
}
}
}
System.out.println("Shortest distances from source:");
for (int i = 0; i < V; i++) {
System.out.println("To " + i + ": " + dist[i]);
}
}
public static void main(String[] args) {
DijkstraAlgorithm graph = new DijkstraAlgorithm(9);
graph.addEdge(0, 1, 4);
graph.addEdge(0, 7, 8);
graph.addEdge(1, 2, 8);
graph.addEdge(1, 7, 11);
graph.addEdge(2, 3, 7);
graph.addEdge(2, 5, 4);
graph.addEdge(2, 8, 2);
graph.addEdge(3
, 4, 9); graph.addEdge(3, 5, 14); graph.addEdge(4, 5, 10); graph.addEdge(5, 6, 2); graph.addEdge(6, 7, 1); graph.addEdge(6, 8, 6); graph.addEdge(7, 8, 7);
graph.dijkstra(0); // Starting from vertex 0
}
}
#### ব্যাখ্যা:
- **PriorityQueue** ব্যবহার করে প্রতিটি নোডের সবচেয়ে ছোট ডিস্ট্যান্স পাথ একে একে বের করা হয়।
- **Dijkstra's Algorithm** গ্রাফে একক সোর্স থেকে সবচেয়ে কম খরচের পথ বের করে দেয়।
#### আউটপুট:
Shortest distances from source: To 0: 0 To 1: 4 To 2: 12 To 3: 19 To 4: 21 To 5: 11 To 6: 9 To 7: 8 To 8: 14
---
### সারাংশ
**Minimum Spanning Tree (MST)** এবং **Shortest Path** অ্যালগরিদমগুলি গ্রাফ তত্ত্বের গুরুত্বপূর্ণ সমস্যা এবং Java তে **Kruskal’s Algorithm**, **Prim’s Algorithm**, **Dijkstra’s Algorithm**, এবং **Bellman-Ford Algorithm** ব্যবহার করে এই সমস্যাগুলির সমাধান করা যায়।
1. **MST** এর জন্য **Kruskal’s** এবং **Prim’s** অ্যালগরিদম ব্যবহৃত হয়, যা গ্রাফের একটি কম ওজনের সাবগ্রাফ তৈরি করতে সহায়তা করে।
2. **Shortest Path** অ্যালগরিদমের মধ্যে **Dijkstra’s** এবং **Bellman-Ford** গ্রাফে একক সোর্স থেকে সমস্ত গন্তব্যের মধ্যে সবচেয়ে ছোট পথ নির্ধারণ করতে ব্যবহৃত হয়।
Read more
