গ্রাফ (Graph in C) গাইড ও নোট

গ্রাফ (Graph in C)

গ্রাফ (Graph) হল একটি গাণিতিক কাঠামো যা ভেরটেক্স (vertices) এবং তাদের মধ্যে সংযোগকারী এজ (edges) দিয়ে গঠিত। গ্রাফ বিভিন্ন বাস্তব জীবনের সমস্যা সমাধানে ব্যবহৃত হয়, যেমন নেটওয়ার্ক ডিভাইসের মধ্যে সংযোগ, রুটিং অ্যালগরিদম, সোসাল নেটওয়ার্কের সম্পর্ক ইত্যাদি। গ্রাফের বিভিন্ন প্রকার রয়েছে যেমন অরডিনারি গ্রাফ, ডিরেক্টেড গ্রাফ, আনডিরেক্টেড গ্রাফ, ওজনযুক্ত গ্রাফ, এবং আরও অনেক।

গ্রাফের মৌলিক ধারণা:

1. ভেরটেক্স (Vertex): গ্রাফের একেকটি বিন্দু বা পয়েন্ট, যেখানে কোনো তথ্য বা উপাদান থাকতে পারে।
2. এজ (Edge): দুটি ভেরটেক্সের মধ্যে সংযোগ। এটি হতে পারে ডিরেক্টেড (Directed) বা আনডিরেক্টেড (Undirected)।
3. ওজন (Weight): কিছু গ্রাফে, এজের মধ্যে ওজন থাকতে পারে যা দুটি ভেরটেক্সের মধ্যে সংযোগের গুরুত্ব বা দৈর্ঘ্য নির্দেশ করে।

গ্রাফের প্রকারভেদ:

1. অরডিনারি গ্রাফ (Ordinary Graph): সাধারণ গ্রাফ যেখানে এজের কোনো নির্দিষ্ট দিক নেই।
2. ডিরেক্টেড গ্রাফ (Directed Graph): গ্রাফের প্রতিটি এজের একটি দিক থাকে, অর্থাৎ এজটি এক ভেরটেক্স থেকে অন্য ভেরটেক্সের দিকে নির্দেশিত থাকে।
3. আনডিরেক্টেড গ্রাফ (Undirected Graph): এজের কোন নির্দিষ্ট দিক নেই, অর্থাৎ দুটি ভেরটেক্সের মধ্যে সংযোগ দ্বিমুখী হয়।
4. ওজনযুক্ত গ্রাফ (Weighted Graph): এজগুলির সাথে কিছু সংখ্যাসূচক মান (ওজন) যুক্ত থাকে।

গ্রাফের উপস্থাপন

গ্রাফ উপস্থাপনের দুটি সাধারণ পদ্ধতি রয়েছে:

1. এ্যাডজাসেন্সি ম্যাট্রিক্স (Adjacency Matrix): একটি 2D অ্যারে, যেখানে গ্রাফের ভেরটেক্সগুলি সারি এবং কলামে থাকে। যদি দুটি ভেরটেক্সের মধ্যে এজ থাকে, তবে তাদের মধ্যে সম্পর্কের স্থানে ১ বা কোনো মান থাকে।
2. এ্যাডজাসেন্সি লিস্ট (Adjacency List): প্রতিটি ভেরটেক্সের জন্য একটি লিস্ট, যা তার সংযুক্ত ভেরটেক্সগুলোকে তালিকাভুক্ত করে।

গ্রাফের সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন

এখানে একটি সাধারণ আনডিরেক্টেড গ্রাফ এবং এ্যাডজাসেন্সি লিস্ট ব্যবহারের উদাহরণ দেওয়া হলো।

Undirected Graph using Adjacency List:

#include <stdio.h>
#include <stdlib.h>

// Structure to represent a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure to represent a graph
struct Graph {
    int numVertices;
    struct Node** adjLists;
};

// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

    // Initialize each adjacency list to NULL
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// Function to create a new node in the adjacency list
struct Node* createNode(int vertex) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// Function to add an edge between two vertices in the graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add an edge from dest to src (since it is undirected)
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Function to print the graph's adjacency list
void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph(5); // Create a graph with 5 vertices

    addEdge(graph, 0, 1); // Add edges
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);

    printGraph(graph); // Print the graph

    return 0;
}

ব্যাখ্যা:

1. Graph Structure:
   • এখানে একটি গ্রাফ তৈরি করা হয়েছে, যার মধ্যে প্রতিটি ভেরটেক্সের জন্য একটি লিঙ্কড লিস্ট রয়েছে যা সেই ভেরটেক্সের সংযুক্ত ভেরটেক্সগুলোকে নির্দেশ করে।
   • createGraph() ফাংশনটি একটি নতুন গ্রাফ তৈরি করে এবং প্রতিটি ভেরটেক্সের জন্য NULL দিয়ে শুরু হয়।
2. addEdge Function:
   • addEdge() ফাংশনটি একটি এজ যোগ করার কাজ করে। এটি প্রথমে src থেকে dest এ একটি এজ যোগ করে, তারপর dest থেকে src এর দিকে আরেকটি এজ যোগ করে (কারণ এটি আনডিরেক্টেড গ্রাফ)।
3. Print Graph:
   • printGraph() ফাংশনটি গ্রাফের সমস্ত ভেরটেক্স এবং তাদের সংযুক্ত নোডগুলো (এজ) প্রদর্শন করে।

উদাহরণ আউটপুট:

Vertex 0: 4 -> 1 -> NULL
Vertex 1: 4 -> 3 -> 2 -> 0 -> NULL
Vertex 2: 3 -> 1 -> NULL
Vertex 3: 2 -> 1 -> NULL
Vertex 4: 1 -> 0 -> NULL

গ্রাফের অন্যান্য অপারেশনসমূহ:

1. ডেপথ-ফার্স্ট সার্চ (DFS):
   • গ্রাফের একটি ভেরটেক্স থেকে শুরু করে, যতটুকু সম্ভব গভীরে চলে যাওয়া, এবং তার পরবর্তী সংযুক্ত নোডগুলো একে একে পরিদর্শন করা।
2. ব্রেডথ-ফার্স্ট সার্চ (BFS):
   • গ্রাফের একটি ভেরটেক্স থেকে শুরু করে, একে একে তার সমস্ত প্রতিবেশী ভেরটেক্স পরিদর্শন করা এবং এরপর তাদের প্রতিবেশী ভেরটেক্সগুলো পরিদর্শন করা।
3. গ্রাফ ট্রাভার্সাল (Graph Traversal):
   • গ্রাফের সমস্ত ভেরটেক্স এবং এজগুলোকে পরিদর্শন করার প্রক্রিয়া। এটি DFS বা BFS দ্বারা করা হয়।

সারসংক্ষেপ:

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

গ্রাফ এর মৌলিক ধারণা এবং প্রকারভেদ

গ্রাফ (Graph) একটি নন-লিনিয়ার ডেটা স্ট্রাকচার যা বিভিন্ন ভেরটেক্স (vertices) এবং তাদের মধ্যে সংযোগকারী এজ (edges) দ্বারা গঠিত। গ্রাফের মধ্যে ভেরটেক্স (যাকে নোড বা শীর্ষও বলা হয়) বিভিন্ন উপাদান বা অবজেক্টকে প্রতিনিধিত্ব করে এবং এজ (edge) দ্বারা তাদের মধ্যে সম্পর্ক বা সংযোগ স্থাপিত হয়। গ্রাফের বিভিন্ন প্রকারভেদ রয়েছে, যেগুলি গ্রাফের কাঠামো, কার্যকারিতা এবং প্রয়োগের উপর ভিত্তি করে আলাদা করা হয়।

গ্রাফ এর মৌলিক ধারণা:

1. ভেরটেক্স (Vertex or Node):
   • গ্রাফের একটি মৌলিক উপাদান যা কোন অবজেক্ট বা ডেটাকে প্রতিনিধিত্ব করে।
   • উদাহরণ: একটি শহর, একটি ব্যক্তি বা একটি প্রতিষ্ঠান।
2. এজ (Edge):
   • দুটি ভেরটেক্সের মধ্যে সংযোগ স্থাপনকারী একটি রেখা বা লিংক।
   • উদাহরণ: দুটি শহরের মধ্যে সড়ক, দুটি প্রতিষ্ঠানের মধ্যে যোগাযোগ লাইন।
3. গ্রাফের গঠন:
   • গ্রাফের মধ্যে একাধিক ভেরটেক্স থাকে এবং তাদের মধ্যে সংযোগ স্থাপন করার জন্য একাধিক এজ ব্যবহার করা হয়।

গ্রাফের প্রকারভেদ:

গ্রাফকে বিভিন্ন দৃষ্টিকোণ থেকে শ্রেণিবদ্ধ করা যায়। এর মধ্যে গুরুত্বপূর্ণ প্রকারভেদগুলো হলো:

১. অপ্রতিরোধী গ্রাফ (Undirected Graph)

• বর্ণনা: অপ্রতিরোধী গ্রাফে, এজের কোন নির্দিষ্ট দিক থাকে না। অর্থাৎ, দুটি ভেরটেক্সের মধ্যে সম্পর্ক উভয় দিকেই সমান থাকে।
• উদাহরণ: শহরের মধ্যে দুটি রাস্তা, যেখানে কোনো দিকের পার্থক্য নেই।

গঠন:

• যদি দুটি ভেরটেক্স \(V_1\) এবং \(V_2\) থাকে, এবং তাদের মধ্যে একটি এজ থাকে, তবে \(V_1 \leftrightarrow V_2\) হিসেবে উল্লেখ করা হয়।

উদাহরণ:

A ----- B
|       |
C ----- D

২. দ্বিমুখী গ্রাফ (Directed Graph or Digraph)

• বর্ণনা: দ্বিমুখী গ্রাফে, এজের একটি নির্দিষ্ট দিক থাকে। অর্থাৎ, একটি ভেরটেক্স থেকে অন্য ভেরটেক্সে যাত্রা করা সম্ভব হলেও বিপরীত দিকটি নির্দিষ্টভাবে উল্লেখিত থাকতে হবে।
• উদাহরণ: ইন্টারনেটের লিঙ্ক, যেখানে একটি ওয়েবপেজ অন্য ওয়েবপেজে রিডাইরেক্ট করতে পারে, কিন্তু বিপরীত দিকটি স্বয়ংক্রিয়ভাবে ঘটে না।

গঠন:

• \(V_1 \rightarrow V_2\) বা \(V_1 \leftarrow V_2\) দ্বারা নির্দেশ করা হয়।

উদাহরণ:

A ---> B
^     |
|     v
C <--- D

৩. ওজনযুক্ত গ্রাফ (Weighted Graph)

• বর্ণনা: এজের সাথে একটি নির্দিষ্ট ওজন থাকে, যা সেই এজের গুরুত্ব বা খরচ বুঝায়। এটি বিশেষত গ্রাফ থিওরির বিভিন্ন অ্যালগরিদমের জন্য ব্যবহার করা হয়, যেমন শর্টেস্ট পাথ ফাইন্ডিং অ্যালগরিদম।
• উদাহরণ: দুইটি শহরের মধ্যে রাস্তা, যেখানে রাস্তার দৈর্ঘ্য বা ব্যয়ের ওপর ভিত্তি করে ওজন নির্ধারণ করা হয়।

গঠন:

• এজের সঙ্গে একটি মান যোগ করা হয়, যেমন \(A \xrightarrow{5} B\), যেখানে ৫ হচ্ছে এজের ওজন।

উদাহরণ:

A ---5---> B
^           |
|           3
|           v
C <---2---- D

৪. সম্পূর্ণ গ্রাফ (Complete Graph)

• বর্ণনা: সম্পূর্ণ গ্রাফে, প্রতিটি ভেরটেক্স অন্য প্রতিটি ভেরটেক্সের সাথে সংযুক্ত থাকে। অর্থাৎ, প্রতিটি ভেরটেক্সের মধ্যে একটি এজ থাকে।
• উদাহরণ: একটি ছোট দলের সকল সদস্য একে অপরের সাথে যোগাযোগ রাখে।

গঠন:

• একটি \(n\)-ভেরটেক্স সম্পূর্ণ গ্রাফের মোট \(\frac{n(n-1)}{2}\) এজ থাকবে (অপ্রতিরোধী গ্রাফের ক্ষেত্রে)।

উদাহরণ:

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

৫. অবস্থানশূন্য গ্রাফ (Sparse Graph) ও ঘন গ্রাফ (Dense Graph)

• বর্ণনা:
  • অবস্থানশূন্য গ্রাফ (Sparse Graph): যেখানে মোট এজের সংখ্যা ভেরটেক্সের সংখ্যা অনুযায়ী কম।
  • ঘন গ্রাফ (Dense Graph): যেখানে মোট এজের সংখ্যা অনেক বেশি থাকে এবং ভেরটেক্সের মধ্যে অধিক সংযোগ থাকে।

গ্রাফের অন্যান্য প্রকারভেদ:

৬. বাইपার্টাইট গ্রাফ (Bipartite Graph)

• বর্ণনা: বাইপার্টাইট গ্রাফে ভেরটেক্সগুলোকে দুটি গ্রুপে ভাগ করা যায়, যেখানে একটি গ্রুপের ভেরটেক্সের সাথে অন্য গ্রুপের ভেরটেক্সের সংযোগ থাকে, কিন্তু একটি গ্রুপের ভেরটেক্সের মধ্যে কোনো সংযোগ নেই।

উদাহরণ:

A --- B
|     |
C --- D

৭. সাইকেলযুক্ত গ্রাফ (Cyclic Graph) ও সাইকেলবিহীন গ্রাফ (Acyclic Graph)

• বর্ণনা:
  • সাইকেলযুক্ত গ্রাফ: যেখানে কোনো একটি ভেরটেক্স থেকে শুরু করে, আবার সেই ভেরটেক্সে ফিরে আসার জন্য কিছু এজ রয়েছে।
  • সাইকেলবিহীন গ্রাফ: যেখানে কোনো সাইকেল বা লুপ থাকে না। এটি একটি দ্বিমুখী গ্রাফ (Directed Acyclic Graph বা DAG) হতে পারে, যেটি অনেক অ্যালগরিদমে ব্যবহার করা হয়।

গ্রাফের প্রয়োগ:

গ্রাফের বিভিন্ন প্রকারভেদ বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়, যেমন:

1. কম্পিউটার নেটওয়ার্ক: গ্রাফ ব্যবহার করা হয় নেটওয়ার্কে কম্পিউটার ও সার্ভারের সংযোগের সম্পর্ক বোঝানোর জন্য।
2. সোশ্যাল নেটওয়ার্ক: বন্ধুদের মধ্যে সম্পর্ক বা ফলোয়ারদের মধ্যে সংযোগ বোঝাতে গ্রাফ ব্যবহৃত হয়।
3. ভ্রমণ এবং পথfinding: শহরের মধ্যে সড়ক সম্পর্ক বা ট্রেনের রুট খোঁজা।
4. ট্রাফিক ফ্লো বা সিডিউলিং: ট্রাফিকের জন্য রাস্তা বা সময়সূচী নির্ধারণের ক্ষেত্রে গ্রাফের ব্যবহার।
5. কম্পাইলার ডিজাইন: DAG (Directed Acyclic Graph) কম্পাইলার অপটিমাইজেশনের জন্য ব্যবহৃত হয়।

সারসংক্ষেপ

গ্রাফ একটি শক্তিশালী ডেটা স্ট্রাকচার যা বাস্তবজীবনের বিভিন্ন সমস্যা মডেলিং করতে সাহায্য করে। গ্রাফের মৌলিক উপাদান হলো ভেরটেক্স এবং এজ। গ্রাফের প্রধান প্রকারভেদগুলোর মধ্যে অপ্রতিরোধী গ্রাফ, দ্বিমুখী গ্রাফ, ওজনযুক্ত গ্রাফ, সম্পূর্ণ গ্রাফ, বাইপার্টাইট গ্রাফ, সাইকেলযুক্ত গ্রাফ এবং সাইকেলবিহীন গ্রাফ অন্যতম। গ্রাফের প্রকারভেদগুলির সঠিক ব্যবহার বিভিন্ন প্রোগ্রামিং সমস্যা এবং অ্যালগরিদমের জন্য গুরুত্বপূর্ণ।

গ্রাফ মডেলিং: 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 হবে।

ধাপ:

1. একটি 2D অ্যারে তৈরি করুন যার সাইজ V x V (V হচ্ছে ভেরটেক্সের সংখ্যা)।
2. যদি ভেরটেক্স 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

সারসংক্ষেপ

• Adjacency Matrix একটি 2D অ্যারে ভিত্তিক গ্রাফ মডেলিং পদ্ধতি, যেখানে প্রতিটি ভেরটেক্সের জন্য একটি ম্যাট্রিক্সের মাধ্যমে সংযোগ প্রদর্শিত হয়। এটি ঘন গ্রাফের জন্য উপযুক্ত।
• Adjacency List একটি গ্রাফ মডেলিং পদ্ধতি যেখানে প্রতিটি ভেরটেক্সের জন্য একটি লিঙ্কড লিস্ট থাকে, এবং এটি সাধারণত সাশ্রয়ী এবং স্পার্স (sparse) গ্রাফের জন্য উপযুক্ত।

এটি আপনার প্রয়োজনে সবচেয়ে উপযুক্ত গ্রাফ মডেলিং পদ্ধতি নির্বাচন করতে সাহায্য করবে।

গ্রাফ ট্র্যাভার্সাল টেকনিকস: BFS (Breadth-First Search), DFS (Depth-First Search)

গ্রাফ ট্র্যাভার্সাল হল এমন একটি প্রক্রিয়া যার মাধ্যমে একটি গ্রাফের সবগুলো নোড বা শীর্ষ (vertex) পরিদর্শন করা হয়। দুটি প্রধান গ্রাফ ট্র্যাভার্সাল টেকনিক হল BFS (Breadth-First Search) এবং **DFS (Depth-First Search)**। এই দুটি টেকনিক গ্রাফের শীর্ষগুলো পরিদর্শন করার জন্য ভিন্ন ভিন্ন পদ্ধতি ব্যবহার করে।

1. BFS (Breadth-First Search)

BFS একটি গ্রাফ ট্র্যাভার্সাল অ্যালগরিদম যা স্তরভিত্তিক (level-wise) গ্রাফের নোড পরিদর্শন করে। অর্থাৎ, BFS প্রথমে এক্সপ্লোর করে একটি নোডের সমস্ত নিকটবর্তী (adjacent) নোডগুলো এবং তারপর একে একে পরবর্তী স্তরের নোডগুলো পরিদর্শন করে।

BFS এর কাজের প্রক্রিয়া:

• BFS একটি queue (কিউ) ব্যবহার করে। শুরুতে একটি শীর্ষ (vertex) কিউতে ঢোকানো হয়।
• কিউ থেকে একটি শীর্ষ নেয়া হয়, এবং তার সমস্ত প্রতিবেশী শীর্ষ কিউতে যুক্ত করা হয় যদি তারা আগে থেকে পরিদর্শিত না হয়ে থাকে।
• এই প্রক্রিয়া তখন পর্যন্ত চলতে থাকে যতক্ষণ না কিউ শূন্য হয়ে যায়।

BFS-এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 5

int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0}
};

void bfs(int start) {
    bool visited[MAX_VERTICES] = {false};
    int queue[MAX_VERTICES], front = 0, rear = 0;
    
    queue[rear++] = start;
    visited[start] = true;

    printf("BFS Traversal: ");
    
    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        for (int i = 0; i < MAX_VERTICES; i++) {
            if (adjMatrix[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
    printf("\n");
}

int main() {
    bfs(0); // Starting from vertex 0
    return 0;
}

Output:

BFS Traversal: 0 1 4 2 3 

BFS এর সুবিধা:

• BFS সর্বনিম্ন স্তরের নোডগুলি প্রথমে পরিদর্শন করে।
• সেরা পথ বা সর্বনিম্ন সংযোগের সমস্যাগুলোর জন্য উপকারী।

2. DFS (Depth-First Search)

DFS একটি গ্রাফ ট্র্যাভার্সাল অ্যালগরিদম যা গ্রাফের একটি শাখার শেষ পর্যন্ত চলে যায় এবং তারপর অন্য শাখায় চলে যায়। DFS প্রথমে একটি নোড নির্বাচন করে, এবং যতদূর সম্ভব তার একটি শাখায় চলে যায়, তারপর ফিরে এসে অন্য শাখায় চলে যায়।

DFS এর কাজের প্রক্রিয়া:

• DFS একটি stack (স্ট্যাক) ব্যবহার করে। এটি একটি নোড থেকে শুরু করে তার যতটা সম্ভব গভীরে যায়, তারপর সেই শাখা শেষ হলে একে একে পূর্ববর্তী শাখায় ফিরে আসে এবং পরবর্তী শাখায় চলে যায়।
• DFS সাধারনত পুনরাবৃত্তি (recursion) অথবা স্ট্যাক ব্যবহার করে বাস্তবায়িত হয়।

DFS-এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 5

int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0}
};

void dfs(int start, bool visited[MAX_VERTICES]) {
    visited[start] = true;
    printf("%d ", start);

    for (int i = 0; i < MAX_VERTICES; i++) {
        if (adjMatrix[start][i] == 1 && !visited[i]) {
            dfs(i, visited);
        }
    }
}

int main() {
    bool visited[MAX_VERTICES] = {false};
    printf("DFS Traversal: ");
    dfs(0, visited); // Starting from vertex 0
    printf("\n");
    return 0;
}

Output:

DFS Traversal: 0 1 2 3 4 

DFS এর সুবিধা:

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

BFS এবং DFS এর মধ্যে পার্থক্য:

সারসংক্ষেপ:

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

গ্রাফের প্রয়োগ: 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 এর প্রক্রিয়া:

1. শুরুতে একটি প্রাথমিক নোড (সোর্স) থেকে সব নোডের দূরত্ব শূন্য (বা অসীম) হিসেবে সেট করা হয়।
2. সর্বোচ্চ প্রাইরিটি নোড নির্বাচন করা হয় এবং তার সাথে সম্পর্কিত সব নোডের দূরত্ব আপডেট করা হয়।
3. পরবর্তী নোডটি নির্বাচন করে একই প্রক্রিয়া পুনরাবৃত্তি করা হয় যতক্ষণ না সব নোডের দূরত্ব নির্ধারিত হয়।

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 তৈরির জন্য দুটি প্রধান অ্যালগরিদম:

1. Kruskal's Algorithm:
   • Kruskal's অ্যালগরিদম একটি গ্রীড ভিত্তিক অ্যালগরিদম যা প্রথমে সমস্ত এজগুলোকে ওজনের উপর সাজায়, তারপর একটি সাইকেল তৈরি না হয় এমনভাবে এজগুলোকে নির্বাচিত করে।
   • এটি একটি গ্রীড ভিত্তিক অ্যালগরিদম এবং প্রতিটি এজকে স্বতন্ত্রভাবে নির্বাচন করে।
2. 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 তৈরি করে, এবং সব নোডের মধ্যে সবচেয়ে কম ওজনের এজ নির্বাচন করে গাছটি সম্প্রসারিত করে।

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