গ্রাফ মডেলিং: Adjacency Matrix এবং Adjacency List
গ্রাফ একটি নন-লিনিয়ার ডেটা স্ট্রাকচার যা ভেরটেক্স (vertices) এবং তাদের মধ্যে সংযোগকারী এজ (edges) দ্বারা গঠিত। গ্রাফ মডেলিং এমন একটি প্রক্রিয়া যা গ্রাফের গঠন এবং এর সংযোগগুলোকে একটি নির্দিষ্ট ডেটা স্ট্রাকচারে প্রজেক্ট করে। গ্রাফ মডেলিংয়ের জন্য সাধারণত দুটি পদ্ধতি ব্যবহৃত হয়: Adjacency Matrix এবং Adjacency List।
১. Adjacency Matrix
Adjacency Matrix একটি 2D অ্যারে (ম্যাট্রিক্স) যা একটি গ্রাফের প্রতিটি ভেরটেক্সের মধ্যে সম্পর্ক বা সংযোগ প্রতিনিধিত্ব করে। এই ম্যাট্রিক্সে, matrix[i][j] মানে হল যে ভেরটেক্স i এবং ভেরটেক্স j এর মধ্যে একটি এজ আছে কিনা।
গঠন:
- যদি গ্রাফটি ডিরেক্টেড (directed) হয়, তাহলে
matrix[i][j] = 1বাmatrix[i][j] = 0এর মাধ্যমে নির্দেশ করা হয় যেiথেকেjতে একটি এজ রয়েছে কিনা। - যদি গ্রাফটি আনডিরেক্টেড (undirected) হয়, তাহলে
matrix[i][j] = 1এবংmatrix[j][i] = 1হবে।
ধাপ:
- একটি 2D অ্যারে তৈরি করুন যার সাইজ
V x V(V হচ্ছে ভেরটেক্সের সংখ্যা)। - যদি ভেরটেক্স
iএবং ভেরটেক্সjএর মধ্যে এজ থাকে, তাহলেmatrix[i][j]তে1সেট করুন, অন্যথায়0রাখুন।
উদাহরণ:
ধরা যাক আমাদের একটি গ্রাফ রয়েছে, যার 4টি ভেরটেক্স (A, B, C, D) এবং এজসমূহ (A -> B, B -> C, C -> D, D -> A)। এর জন্য Adjacency Matrix হবে:
A B C D
A [ 0, 1, 0, 0 ]
B [ 0, 0, 1, 0 ]
C [ 0, 0, 0, 1 ]
D [ 1, 0, 0, 0 ]সি প্রোগ্রামে Adjacency Matrix এর ইমপ্লিমেন্টেশন:
#include <stdio.h>
#define V 4 // ভেরটেক্সের সংখ্যা
void printMatrix(int graph[V][V]) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
int main() {
int graph[V][V] = {
{0, 1, 0, 0},
{0, 0, 1, 0},
{0, 0, 0, 1},
{1, 0, 0, 0}
};
printf("Adjacency Matrix:\n");
printMatrix(graph);
return 0;
}২. Adjacency List
Adjacency List গ্রাফের একটি বহুল ব্যবহৃত উপস্থাপন পদ্ধতি, যেখানে প্রতিটি ভেরটেক্সের জন্য একটি লিঙ্কড লিস্ট (বা অ্যারে) থাকে, এবং ওই লিস্টে সেই ভেরটেক্সের সাথে সংযুক্ত সব ভেরটেক্সের রেফারেন্স থাকে। এই পদ্ধতিতে, গ্রাফের সংযোগগুলি কেবলমাত্র যে ভেরটেক্সগুলির মধ্যে একটি সম্পর্ক আছে তাদের মধ্যে সংরক্ষিত হয়, ফলে মেমরি দক্ষতা বৃদ্ধি পায়।
গঠন:
- প্রতিটি ভেরটেক্স একটি লিস্ট ধারণ করে, এবং প্রতিটি লিস্টের মধ্যে ভেরটেক্সের সাথে সংযুক্ত অন্যান্য ভেরটেক্সের মান থাকবে।
উদাহরণ:
ধরা যাক আমাদের একটি গ্রাফ রয়েছে, যার 4টি ভেরটেক্স (A, B, C, D) এবং এজসমূহ (A -> B, B -> C, C -> D, D -> A)। এর জন্য Adjacency List হবে:
A -> B
B -> C
C -> D
D -> Aসি প্রোগ্রামে Adjacency List এর ইমপ্লিমেন্টেশন:
#include <stdio.h>
#include <stdlib.h>
// গ্রাফের জন্য নোড স্ট্রাকচার
struct Node {
int vertex;
struct Node* next;
};
// গ্রাফের জন্য অ্যাডজেসেন্সি লিস্ট
struct Graph {
int V;
struct Node** adjList;
};
// নতুন নোড তৈরি
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// গ্রাফ তৈরি
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->adjList = (struct Node**)malloc(V * sizeof(struct Node*));
for (int i = 0; i < V; i++) {
graph->adjList[i] = NULL;
}
return graph;
}
// একটি এজ যুক্ত করা
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
}
// গ্রাফ প্রিন্ট করা
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->V; i++) {
struct Node* temp = graph->adjList[i];
printf("\nVertex %d: ", i);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("NULL\n");
}
}
int main() {
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1); // A -> B
addEdge(graph, 1, 2); // B -> C
addEdge(graph, 2, 3); // C -> D
addEdge(graph, 3, 0); // D -> A
printGraph(graph);
return 0;
}Comparing Adjacency Matrix and Adjacency List
| Property | Adjacency Matrix | Adjacency List |
|---|---|---|
| Memory Usage | Requires O(V^2) space, where V is the number of vertices | Requires O(V + E) space, where E is the number of edges |
| Space Efficiency | Less efficient for sparse graphs | More efficient for sparse graphs |
| Accessing Edge | O(1) for checking if there is an edge | O(V) in the worst case for finding a specific edge |
| Adding Edge | O(1) if indices are known | O(1) for adding an edge in the list |
| Deleting Edge | O(1) for deleting an edge | O(V) for deleting an edge (if not doubly linked) |
সারসংক্ষেপ
- Adjacency Matrix একটি 2D অ্যারে ভিত্তিক গ্রাফ মডেলিং পদ্ধতি, যেখানে প্রতিটি ভেরটেক্সের জন্য একটি ম্যাট্রিক্সের মাধ্যমে সংযোগ প্রদর্শিত হয়। এটি ঘন গ্রাফের জন্য উপযুক্ত।
- Adjacency List একটি গ্রাফ মডেলিং পদ্ধতি যেখানে প্রতিটি ভেরটেক্সের জন্য একটি লিঙ্কড লিস্ট থাকে, এবং এটি সাধারণত সাশ্রয়ী এবং স্পার্স (sparse) গ্রাফের জন্য উপযুক্ত।
এটি আপনার প্রয়োজনে সবচেয়ে উপযুক্ত গ্রাফ মডেলিং পদ্ধতি নির্বাচন করতে সাহায্য করবে।
Read more
