গ্রাফের প্রয়োগ: Shortest Path (Dijkstra's Algorithm), Minimum Spanning Tree (Kruskal's এবং Prim's Algorithm)
গ্রাফ থিওরি কম্পিউটার সায়েন্স এবং সফটওয়্যার ইঞ্জিনিয়ারিংয়ে গুরুত্বপূর্ণ ভূমিকা পালন করে। এটি বিভিন্ন ধরনের সমস্যার সমাধানে ব্যবহৃত হয়, যেমন Shortest Path এবং Minimum Spanning Tree। এই দুটি অ্যালগরিদম বাস্তব জীবনের অনেক সমস্যার সমাধান করতে সহায়তা করে, যেমন রুট নকশা, নেটওয়ার্ক ডিজাইন, এবং ট্র্যাফিক নিয়ন্ত্রণ। নিচে এই দুটি গুরুত্বপূর্ণ অ্যালগরিদমের বিস্তারিত আলোচনা করা হলো।
1. Shortest Path (Dijkstra's Algorithm)
Dijkstra's Algorithm একটি গ্রাফের মধ্যে দুটি নোডের মধ্যে সবচেয়ে স্বল্প দূরত্ব খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি অগ্রগতির মাধ্যমে কাজ করে, যেখানে সর্বোচ্চ প্রাইরিটি (সর্বনিম্ন দূরত্ব) নোডটি নির্বাচন করা হয় এবং তার পরবর্তী নোডগুলোর জন্য আপডেট করা হয়।
Dijkstra's Algorithm এর প্রক্রিয়া:
- শুরুতে একটি প্রাথমিক নোড (সোর্স) থেকে সব নোডের দূরত্ব শূন্য (বা অসীম) হিসেবে সেট করা হয়।
- সর্বোচ্চ প্রাইরিটি নোড নির্বাচন করা হয় এবং তার সাথে সম্পর্কিত সব নোডের দূরত্ব আপডেট করা হয়।
- পরবর্তী নোডটি নির্বাচন করে একই প্রক্রিয়া পুনরাবৃত্তি করা হয় যতক্ষণ না সব নোডের দূরত্ব নির্ধারিত হয়।
Dijkstra's Algorithm এর সি কোড:
#include <stdio.h>
#include <limits.h>
#define V 9 // Number of vertices
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// Dijkstra's algorithm implementation
void dijkstra(int graph[V][V], int src) {
int dist[V]; // Shortest distance from source
int sptSet[V]; // Shortest path tree set
// Initialize all distances as INFINITE and sptSet as false
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0; // Distance from source to itself is always 0
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet); // Pick the minimum distance vertex from the set
sptSet[u] = 1; // Mark the picked vertex as processed
// Update dist[] values of the adjacent vertices
for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the distance array
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++) {
printf("%d \t %d\n", i, dist[i]);
}
}
int main() {
// Example graph
int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 0, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 0},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 0, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 0, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0); // Source vertex 0
return 0;
}2. Minimum Spanning Tree (MST)
Minimum Spanning Tree (MST) একটি গ্রাফের সব নোডকে সংযুক্ত করার জন্য সবচেয়ে কম প্রাইস বা ওজনের এজের সেট হয়, যেখানে কোন সাইকেল থাকে না। এটি গ্রাফের সব নোডকে যুক্ত করতে একক একটি গাছ তৈরি করে।
MST তৈরির জন্য দুটি প্রধান অ্যালগরিদম:
- Kruskal's Algorithm:
- Kruskal's অ্যালগরিদম একটি গ্রীড ভিত্তিক অ্যালগরিদম যা প্রথমে সমস্ত এজগুলোকে ওজনের উপর সাজায়, তারপর একটি সাইকেল তৈরি না হয় এমনভাবে এজগুলোকে নির্বাচিত করে।
- এটি একটি গ্রীড ভিত্তিক অ্যালগরিদম এবং প্রতিটি এজকে স্বতন্ত্রভাবে নির্বাচন করে।
- Prim's Algorithm:
- Prim's অ্যালগরিদম একটি গাছ-ভিত্তিক অ্যালগরিদম যা একটি একক শুরু নোড থেকে শুরু করে গাছটি ধীরে ধীরে বৃদ্ধি করে, সর্বনিম্ন ওজনের এজগুলো নির্বাচন করে।
Kruskal's Algorithm এর সি কোড:
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
// Structure for Edge
struct Edge {
int src, dest, weight;
};
// Structure for Disjoint Set
struct Subset {
int parent;
int rank;
};
// Function to compare two edges (used in qsort)
int compareEdges(const void* a, const void* b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}
// Function to find the subset of an element
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
// Function to perform union of two subsets
void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Kruskal's algorithm to find MST
void kruskal(struct Edge edges[], int V, int E) {
struct Subset *subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
struct Edge result[V]; // To store the resultant MST
int e = 0; // Count of edges in MST
int i = 0; // Initial index of sorted edges
// Step 1: Sort all the edges in non-decreasing order of weight
qsort(edges, E, sizeof(edges[0]), compareEdges);
// Step 2: Create V subsets with single elements
for (i = 0; i < V; ++i) {
subsets[i].parent = i;
subsets[i].rank = 0;
}
i = 0; // Index of sorted edges
// Step 3: Process each edge
while (e < V - 1 && i < E) {
struct Edge next_edge = edges[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
printf("Following are the edges in the constructed MST:\n");
for (i = 0; i < e; ++i) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}
}
int main() {
int V = 4; // Number of vertices
int E = 5; // Number of edges
struct Edge edges[] = {
{0, 1, 10},
{0
, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
kruskal(edges, V, E);
return 0;
}Prim's Algorithm এর সি কোড:
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices
// Function to find the vertex with the minimum key value
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}
// Function to implement Prim's algorithm
void prim(int graph[V][V]) {
int parent[V]; // Array to store the constructed MST
int key[V]; // Key values used to pick minimum weight edge
bool mstSet[V]; // To represent the vertices included in MST
// Initialize all key values to INF and mstSet[] as false
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0; // Make the first vertex the root of MST
parent[0] = -1; // First node has no parent
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet); // Pick the minimum key vertex
mstSet[u] = true; // Add u to the MST
for (int v = 0; v < V; v++) {
// Update key and parent if the adjacent vertex v is not yet in MST
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
key[v] = graph[u][v];
parent[v] = u;
}
}
}
// Print the constructed MST
printf("Edge \t Weight\n");
for (int i = 1; i < V; i++) {
printf("%d - %d \t %d\n", parent[i], i, graph[i][parent[i]]);
}
}
int main() {
// Example graph
int graph[V][V] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
prim(graph);
return 0;
}সারসংক্ষেপ
- Dijkstra's Algorithm: এটি একটি গ্রাফের মধ্যে সোর্স নোড থেকে সব অন্যান্য নোডের মধ্যে সবচেয়ে ছোট দূরত্ব খুঁজে বের করার জন্য ব্যবহৃত হয়।
- Minimum Spanning Tree (MST):
- Kruskal's Algorithm: এটি সাইকলেস গাছ তৈরি করার জন্য সমস্ত এজ গুলোকে ওজন অনুযায়ী সাজিয়ে এবং সাইকেল তৈরি না হওয়ার নিশ্চয়তা দিয়ে MST তৈরি করে।
- Prim's Algorithm: এটি একটি একক নোড থেকে MST তৈরি করে, এবং সব নোডের মধ্যে সবচেয়ে কম ওজনের এজ নির্বাচন করে গাছটি সম্প্রসারিত করে।
এই তিনটি অ্যালগরিদম গ্রাফ সমস্যা সমাধানে ব্যাপকভাবে ব্যবহৃত হয়, বিশেষত নেটওয়ার্ক ডিজাইন, রুট নির্বাচন, এবং গ্রাফ ট্র্যাভার্সাল সমস্যা সমাধানে।
Content added By
Read more
