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

গ্রাফ (Graph) একটি শক্তিশালী এবং অত্যন্ত গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা নোড (Node) বা ভারটেক্স (Vertex) এবং এজ (Edge) থেকে গঠিত। এটি বিভিন্ন ধরণের সম্পর্ক এবং সংযোগ মডেল করতে ব্যবহৃত হয়। গ্রাফের মধ্যে, নোডগুলি সম্পর্কিত থাকে একে অপরের সাথে, এবং এজগুলির মাধ্যমে তারা সংযুক্ত হয়।

গ্রাফের অ্যাপ্লিকেশনগুলো রয়েছে নেটওয়ার্ক ট্র্যাফিক, রুটিং টেবিল, ফেসবুক বন্ধুদের সম্পর্ক, বিভিন্ন ভ্রমণ পথ, ট্রি স্ট্রাকচার ইত্যাদিতে।

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

গ্রাফের কিছু মৌলিক উপাদান হলো:

1. Vertex (নোড): এটি গ্রাফের একটি পয়েন্ট, যা একটি একক বস্তু প্রতিনিধিত্ব করে।
2. Edge (এজ): এটি দুটি নোডের মধ্যে সংযোগ বা সম্পর্ক প্রতিনিধিত্ব করে।
3. Directed Graph (ডিরেক্টেড গ্রাফ): এই গ্রাফে এজের একটি নির্দিষ্ট দিক থাকে, অর্থাৎ, একটি নোড থেকে অন্য নোডে নির্দেশ করে।
4. Undirected Graph (আন্ডিরেক্টেড গ্রাফ): এই গ্রাফে এজের কোন দিক থাকে না, অর্থাৎ দুইটি নোড একে অপরের সাথে সংযুক্ত থাকে।
5. Weighted Graph: যখন গ্রাফের এজগুলির সাথে ওজন (weight) সংযুক্ত থাকে, যেমন দুটি শহরের মধ্যে দূরত্ব।
6. Unweighted Graph: যখন গ্রাফের এজগুলির সাথে কোনো ওজন (weight) সংযুক্ত না থাকে।
7. Cyclic Graph: যদি একটি গ্রাফে এমন একটি পথ থাকে যা প্রথম নোডে ফিরে আসে, তাহলে সেটি একটি Cyclic Graph।
8. Acyclic Graph: যদি কোনো গ্রাফে এমন কোনো পথ না থাকে যা প্রথম নোডে ফিরে আসে, তাহলে সেটি Acyclic Graph।

2. গ্রাফের ব্যবহার ক্ষেত্রসমূহ

গ্রাফের প্রধান ব্যবহার ক্ষেত্রগুলির মধ্যে রয়েছে:

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

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

গ্রাফ উপস্থাপন করার জন্য প্রধানত দুটি পদ্ধতি ব্যবহৃত হয়:

1. অ্যাডজেসেন্সি ম্যাট্রিক্স (Adjacency Matrix):
   • এটি একটি 2D অ্যারে যা গ্রাফের এজ সম্পর্কিত তথ্য ধারণ করে।
   • যদি দুটি নোডের মধ্যে একটি এজ থাকে, তবে সেই অবস্থানটি 1 হবে, অন্যথায় 0।
2. অ্যাডজেসেন্সি লিস্ট (Adjacency List):
   • এখানে, প্রতিটি নোডের জন্য একটি লিস্ট বা অ্যারে থাকে, যেখানে ওই নোডের সাথে সংযুক্ত অন্য নোডগুলির ইনফরমেশন থাকে।
   • এটি সাধারণত কমপ্যাক্ট এবং কার্যকরী যখন গ্রাফ বড় হয় এবং এজ সংখ্যা কম থাকে।

4. Java তে গ্রাফ উপস্থাপনা

Java তে গ্রাফ উপস্থাপন করার জন্য আমরা Adjacency List ব্যবহার করব।

Java তে গ্রাফের ক্লাস তৈরি (Adjacency List ব্যবহার):

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    // Constructor
    public Graph() {
        adjList = new HashMap<>();
    }

    // Add edge to the graph
    public void addEdge(int source, int destination) {
        adjList.putIfAbsent(source, new ArrayList<>());
        adjList.putIfAbsent(destination, new ArrayList<>());
        adjList.get(source).add(destination); // Directed graph
        adjList.get(destination).add(source); // Uncomment for undirected graph
    }

    // Display the graph
    public void display() {
        for (int vertex : adjList.keySet()) {
            System.out.print(vertex + ": ");
            for (int neighbor : adjList.get(vertex)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    // DFS traversal
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited);
    }

    private void dfsHelper(int vertex, Set<Integer> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");

        for (int neighbor : adjList.get(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }

    // BFS traversal
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(start);
        queue.offer(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int neighbor : adjList.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
}

public class GraphExample {
    public static void main(String[] args) {
        Graph graph = new Graph();

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

        // Display the graph
        System.out.println("Graph adjacency list:");
        graph.display();

        // DFS Traversal
        System.out.println("\nDFS Traversal starting from vertex 1:");
        graph.dfs(1);

        // BFS Traversal
        System.out.println("\nBFS Traversal starting from vertex 1:");
        graph.bfs(1);
    }
}

ব্যাখ্যা:

• Graph ক্লাসে Adjacency List উপস্থাপন করা হয়েছে, যেখানে প্রতিটি নোডের জন্য একটি লিস্ট থাকে যা সংশ্লিষ্ট নোডের এজ গুলি ধারণ করে।
• addEdge() পদ্ধতি দ্বারা গ্রাফে এজ যোগ করা হয়।
• dfs() এবং bfs() পদ্ধতি দ্বারা গ্রাফের Depth-First Search (DFS) এবং Breadth-First Search (BFS) ট্রাভার্সাল করা হয়।
• display() পদ্ধতি গ্রাফের adjacency list প্রদর্শন করে।

আউটপুট:

Graph adjacency list:
1: 2 3 
2: 1 4 
3: 1 4 
4: 2 3 5 
5: 4 

DFS Traversal starting from vertex 1:
1 2 4 3 5 

BFS Traversal starting from vertex 1:
1 2 3 4 5 

5. গ্রাফের অ্যালগরিদম

Depth-First Search (DFS)

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

Breadth-First Search (BFS)

BFS হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা প্রথমে গ্রাফের শীর্ষ নোড থেকে শুরু করে পর্যায়ক্রমে সমস্ত নোড ভিজিট করে। এটি Queue ব্যবহার করে গ্রাফ ট্রাভার্সাল সম্পন্ন করে।

6. গ্রাফে শিখার এবং সমস্যা সমাধানের কিছু উদাহরণ

1. সামাজিক নেটওয়ার্ক: ব্যবহারকারীদের সম্পর্ক মডেল করার জন্য গ্রাফ ব্যবহার করা যায়।
2. রুটিং অ্যালগরিদম: Dijkstra's Algorithm বা Bellman-Ford Algorithm ব্যবহার করে গ্রাফের মধ্যে সেরা রুট খুঁজে বের করা যায়।
3. মাঝে-মাঝে পথ খুঁজে পাওয়া: Shortest Path সমস্যা, যেখানে দুটি নোডের মধ্যে সেরা (সবচেয়ে কম খরচের) পথ খুঁজে বের করা হয়।

সারাংশ

গ্রাফ (Graph) হল একটি অত্যন্ত শক্তিশালী এবং বহুল ব্যবহৃত ডেটা স্ট্রাকচার যা বিভিন্ন ধরনের সম্পর্ক এবং সংযোগ মডেল করার জন্য ব্যবহৃত হয়। Java তে গ্রাফ উপস্থাপন করার জন্য Adjacency List বা Adjacency Matrix ব্যবহার করা যেতে পারে। গ্রাফে বিভিন্ন অ্যালগরিদম যেমন DFS (Depth-First Search) এবং BFS (Breadth-First Search) ব্যবহার করা হয় ট্রাভার্সাল বা অনুসন্ধান করার জন্য। এটি Shortest Path, Cycle Detection, Social Networks ইত্যাদি সমস্যা সমাধানে ব্যবহৃত হয়।

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

Graph এর ধারণা

গ্রাফে দুটি মৌলিক উপাদান থাকে:

1. Nodes (নোড): একে ভেরটিস (vertices)ও বলা হয়। এটি গ্রাফের মূল উপাদান, যার মধ্যে একটি ইউনিক আইডেন্টিফায়ার থাকে। একটি নোড গ্রাফের তথ্য ধারণ করে।
2. Edges (এজ): এটি দুটি নোডের মধ্যে সম্পর্ক বা সংযোগ নির্দেশ করে। একটি এজ নোডগুলোকে সংযুক্ত করে এবং তাদের মধ্যে যোগাযোগের পথ তৈরি করে।

গ্রাফে নোডের সংখ্যা সাধারণত V (vertices) এবং এজের সংখ্যা E (edges) দ্বারা চিহ্নিত করা হয়।

Graph এর প্রকারভেদ

গ্রাফ দুটি প্রধান প্রকারে বিভক্ত হতে পারে:

1. Directed Graph (ডাইরেক্টেড গ্রাফ): যেখানে এজগুলোর একটি নির্দিষ্ট দিক থাকে, অর্থাৎ এক নোড থেকে অন্য নোডে যাওয়ার জন্য একটি নির্দিষ্ট দিক থাকে।
2. Undirected Graph (আন্ডাইরেক্টেড গ্রাফ): যেখানে এজগুলোর কোনো দিক থাকে না, অর্থাৎ এক নোড থেকে অন্য নোডে যাওয়ার পথ দুটি দিকে উন্মুক্ত থাকে।

1. Directed Graph (ডাইরেক্টেড গ্রাফ)

ডাইরেক্টেড গ্রাফ (বা digraph) এমন একটি গ্রাফ, যেখানে প্রতিটি এজের একটি নির্দিষ্ট দিক থাকে। অর্থাৎ, এজের একটি শুরু এবং একটি শেষ নোড থাকে। এখানে, একটি নোড থেকে অন্য নোডে যাওয়া যাবে, তবে এর বিপরীত দিক দিয়ে যাওয়া সম্ভব নাও হতে পারে।

উদাহরণ:

ধরা যাক, গ্রাফে ৩টি নোড রয়েছে এবং তাদের মধ্যে কিছু সম্পর্ক রয়েছে:

• A → B (A থেকে B)
• B → C (B থেকে C)
• C → A (C থেকে A)

এই গ্রাফে A → B সম্পর্কের মানে হল যে A থেকে B তে যাওয়া যায়, তবে B থেকে A তে যাওয়া যাবে না।

ডাইরেক্টেড গ্রাফের সুবিধা:

• দিক নির্ধারণ: নির্দিষ্ট দিক নির্দেশিত সংযোগগুলিকে রূপরেখা করা যায়।
• সোশ্যাল মিডিয়া ও ওয়েব সাইটে: সোশ্যাল মিডিয়া (যেমন ফলোয়ার এবং ফলোয়িং) সম্পর্ক এবং ওয়েব পেজের লিঙ্কের গঠন নির্দেশ করতে ডাইরেক্টেড গ্রাফ ব্যবহার করা হয়।

উদাহরণ কোড:

import java.util.*;

public class DirectedGraph {
    Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int src, int dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.get(src).add(dest);
    }

    public void printGraph() {
        for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
            System.out.print(entry.getKey() + " -> ");
            for (Integer node : entry.getValue()) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph();
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        graph.printGraph();
    }
}

2. Undirected Graph (আন্ডাইরেক্টেড গ্রাফ)

আন্ডাইরেক্টেড গ্রাফে এজের কোনো দিক থাকে না, অর্থাৎ, নোডগুলি একে অপরের সাথে সমানভাবে সংযুক্ত থাকে। অর্থাৎ, যদি একটি এজ A এবং B এর মধ্যে থাকে, তাহলে A থেকে B এবং B থেকে A উভয়ভাবেই যাওয়া সম্ভব।

উদাহরণ:

ধরা যাক, গ্রাফে ৩টি নোড রয়েছে এবং তাদের মধ্যে কিছু সম্পর্ক রয়েছে:

• A - B (A এবং B একে অপরের সাথে সংযুক্ত)
• B - C (B এবং C একে অপরের সাথে সংযুক্ত)
• C - A (C এবং A একে অপরের সাথে সংযুক্ত)

এই গ্রাফে, A থেকে B এবং B থেকে A উভয়ভাবেই যোগাযোগ করা যাবে।

আন্ডাইরেক্টেড গ্রাফের সুবিধা:

• দিকহীন সংযোগ: যেখানে কোনো নির্দিষ্ট দিকের প্রয়োজন নেই, সেখানে আন্ডাইরেক্টেড গ্রাফ কার্যকরী।
• সামাজিক সম্পর্ক: যেমন বন্ধুদের সম্পর্ক, যেখানে দুটি ব্যক্তি একে অপরকে বন্ধু হিসেবে যুক্ত করতে পারেন, তার জন্য আন্ডাইরেক্টেড গ্রাফ ব্যবহৃত হয়।

উদাহরণ কোড:

import java.util.*;

public class UndirectedGraph {
    Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int src, int dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.putIfAbsent(dest, new ArrayList<>());
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    public void printGraph() {
        for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
            System.out.print(entry.getKey() + " -> ");
            for (Integer node : entry.getValue()) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph();
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        graph.printGraph();
    }
}

সারাংশ

Graph (গ্রাফ) হল একটি ডেটা স্ট্রাকচার যা নোড এবং তাদের মধ্যে সংযোগ (এজ) ব্যবহার করে সম্পর্ক নির্ধারণ করে। গ্রাফ দুটি প্রধান প্রকারের হতে পারে:

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

এ দুটি গ্রাফের প্রকার বিভিন্ন ধরনের বাস্তব জীবনের সম্পর্ক এবং সমস্যার সমাধানে ব্যবহৃত হয়।

Graph (গ্রাফ) হলো একটি গাণিতিক কনসেপ্ট যা সিস্টেমের বিভিন্ন উপাদান (যেমন, নোড বা ভারটিস) এবং তাদের মধ্যে সংযোগ (এজ) এর সম্পর্ককে বোঝায়। গ্রাফের মধ্যে বিভিন্ন ধরনের সম্পর্ক থাকতে পারে এবং এটি বিভিন্ন সমস্যা যেমন নেটওয়ার্কিং, সড়ক বা ট্রাফিক ম্যাপ, সোশ্যাল মিডিয়া সম্পর্ক ইত্যাদি মডেল করতে ব্যবহৃত হয়।

গ্রাফ রেপ্রেজেন্টেশনের দুইটি প্রধান পদ্ধতি হলো:

1. Adjacency Matrix
2. Adjacency List

আমরা এই দুটি পদ্ধতি জাভাতে কিভাবে ইমপ্লিমেন্ট করতে পারি তা দেখবো।

১. Adjacency Matrix (এডজেসেন্সি ম্যাট্রিক্স)

Adjacency Matrix একটি 2D অ্যারে দ্বারা গ্রাফের রেপ্রেজেন্টেশন। এই পদ্ধতিতে, গ্রাফের প্রতিটি নোডের জন্য একটি রো এবং কলাম তৈরি হয়, এবং এই রো কলামগুলোকে 1 বা 0 দিয়ে পূর্ণ করা হয়, যেখানে 1 নির্দেশ করে যে দুটি নোডের মধ্যে একটি এজ (Edge) রয়েছে, আর 0 নির্দেশ করে যে দুটি নোডের মধ্যে কোন এজ নেই।

Adjacency Matrix Representation

• 1: দুটি নোডের মধ্যে একটি এজ রয়েছে।
• 0: দুটি নোডের মধ্যে কোন এজ নেই।

উদাহরণ: Adjacency Matrix

ধরা যাক, আমাদের একটি গ্রাফ রয়েছে যেটিতে ৪টি নোড রয়েছে (A, B, C, D), এবং এজগুলি (A-B, A-C, B-D)।

A -- B
|    |
C -- D

এই গ্রাফের জন্য অ্যাডজেসেন্সি ম্যাট্রিক্স হবে:

    A  B  C  D
A  [0, 1, 1, 0]
B  [1, 0, 0, 1]
C  [1, 0, 0, 0]
D  [0, 1, 0, 0]

এখানে, matrix[i][j] মানে হল, i এবং j নোডের মধ্যে একটি এজ আছে কিনা। যদি এজ থাকে তবে সেটি 1, না থাকলে 0।

Java তে Adjacency Matrix ইমপ্লিমেন্টেশন

public class GraphAdjMatrix {
    private int[][] adjMatrix;
    private int numVertices;

    public GraphAdjMatrix(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new int[numVertices][numVertices];
    }

    // Add edge between vertex v1 and v2
    public void addEdge(int v1, int v2) {
        adjMatrix[v1][v2] = 1;
        adjMatrix[v2][v1] = 1;  // Since it's an undirected graph
    }

    // Display the adjacency matrix
    public void displayGraph() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        GraphAdjMatrix graph = new GraphAdjMatrix(4);  // 4 vertices
        graph.addEdge(0, 1);  // Add edge between A and B
        graph.addEdge(0, 2);  // Add edge between A and C
        graph.addEdge(1, 3);  // Add edge between B and D

        graph.displayGraph();
    }
}

আউটপুট:

0 1 1 0 
1 0 0 1 
1 0 0 0 
0 1 0 0

২. Adjacency List (এডজেসেন্সি লিস্ট)

Adjacency List হলো একটি গ্রাফের প্রতিটি নোডের জন্য একটি লিস্ট (বা লিঙ্কড লিস্ট) তৈরি করা, যা সংশ্লিষ্ট নোডগুলির সাথে সংযোগ সম্পর্কিত এজগুলিকে ধারণ করে। এটি সাধারণত ওরিয়েন্টেড অথবা আন্ডিরেক্টেড গ্রাফের জন্য ব্যবহৃত হয়। অ্যাডজেসেন্সি লিস্টে সাধারণত একটি অ্যারে বা লিস্ট থাকে, যেখানে প্রতিটি নোডের জন্য অন্য নোডের লিঙ্ক সংরক্ষিত থাকে।

Adjacency List Representation

• প্রতিটি নোডের জন্য একটি লিস্ট তৈরি করা হয় যা তার সাথে সংযুক্ত অন্যান্য নোডের নাম ধারণ করে।

উদাহরণ: Adjacency List

ধরা যাক, আমাদের একটি গ্রাফ রয়েছে যেটিতে ৪টি নোড রয়েছে (A, B, C, D), এবং এজগুলি (A-B, A-C, B-D)।

A -- B
|    |
C -- D

এই গ্রাফের জন্য অ্যাডজেসেন্সি লিস্ট হবে:

A: B, C
B: A, D
C: A
D: B

Java তে Adjacency List ইমপ্লিমেন্টেশন

import java.util.*;

public class GraphAdjList {
    private Map<Integer, List<Integer>> adjList;
    private int numVertices;

    public GraphAdjList(int numVertices) {
        this.numVertices = numVertices;
        adjList = new HashMap<>();
        for (int i = 0; i < numVertices; i++) {
            adjList.put(i, new LinkedList<>());
        }
    }

    // Add edge between vertex v1 and v2
    public void addEdge(int v1, int v2) {
        adjList.get(v1).add(v2);
        adjList.get(v2).add(v1);  // Since it's an undirected graph
    }

    // Display the adjacency list
    public void displayGraph() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print(i + ": ");
            for (Integer vertex : adjList.get(i)) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        GraphAdjList graph = new GraphAdjList(4);  // 4 vertices
        graph.addEdge(0, 1);  // Add edge between A and B
        graph.addEdge(0, 2);  // Add edge between A and C
        graph.addEdge(1, 3);  // Add edge between B and D

        graph.displayGraph();
    }
}

আউটপুট:

0: 1 2 
1: 0 3 
2: 0 
3: 1

সারাংশ

Adjacency Matrix এবং Adjacency List হলো গ্রাফ রিপ্রেজেন্টেশনের দুটি সাধারণ পদ্ধতি, প্রতিটির নিজস্ব সুবিধা এবং সীমাবদ্ধতা রয়েছে।

• Adjacency Matrix: গ্রাফের সকল সম্পর্ক একসাথে একটি 2D অ্যারেতে সংরক্ষিত থাকে। এটি সোজা এবং নির্দিষ্ট সাইজের গ্রাফের জন্য কার্যকরী, তবে বড় গ্রাফের ক্ষেত্রে মেমরি খরচ বেশি হয়।
• Adjacency List: এটি প্রতিটি নোডের জন্য একটি লিস্ট তৈরি করে যা তার সংযুক্ত নোডগুলির তালিকা সংরক্ষণ করে। এটি মেমরি ইফিশিয়েন্ট এবং অনেক বড় গ্রাফের জন্য উপযুক্ত।

এছাড়া, বিভিন্ন গ্রাফ অ্যালগরিদম (যেমন BFS, DFS, Dijkstra) কার্যকরীভাবে এই রিপ্রেজেন্টেশনগুলির উপর ভিত্তি করে কাজ করে।

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

১. Depth-First Search (DFS)

DFS (Depth-First Search) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি শীর্ষ থেকে শুরু করে যতদূর সম্ভব গভীরতায় যায়, অর্থাৎ একটি শাখার শেষে পৌঁছানো না পর্যন্ত ঐ শাখার সমস্ত শীর্ষ পরিদর্শন করে এবং তারপর অন্য শাখায় চলে যায়।

DFS এর বৈশিষ্ট্য:

• Stack-based: DFS সাধারণত Stack ব্যবহার করে বাস্তবায়িত হয় (যেমন, রিকার্সন ব্যবহার করে)।
• Time Complexity: O(V + E), যেখানে V হল গ্রাফের শীর্ষের সংখ্যা এবং E হল সীমান্তের সংখ্যা।
• Space Complexity: O(V) (স্ট্যাকের কারণে)।

উদাহরণ: DFS Traversal using Recursion

import java.util.*;

public class GraphDFS {
    private Map<Integer, List<Integer>> adjList;

    public GraphDFS() {
        adjList = new HashMap<>();
    }

    // গ্রাফে একটি সীমান্ত যোগ করা
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // DFS Traversal
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsUtil(start, visited);
    }

    // DFS Utility Method
    private void dfsUtil(int v, Set<Integer> visited) {
        visited.add(v); // বর্তমান নোড ভিজিট করা
        System.out.print(v + " ");

        // সংশ্লিষ্ট সমস্ত শীর্ষ পরিদর্শন করা
        for (int neighbor : adjList.getOrDefault(v, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        GraphDFS graph = new GraphDFS();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);

        System.out.println("DFS Traversal starting from vertex 1:");
        graph.dfs(1);
    }
}

ব্যাখ্যা:

• addEdge(v, w): একটি সীমান্ত যোগ করা হয় যা গ্রাফের দুটি শীর্ষ v এবং w এর মধ্যে সংযোগ স্থাপন করে।
• dfsUtil(v, visited): এটি রিকার্সিভভাবে DFS ট্রাভার্সাল পরিচালনা করে।
• visited: এটি একটি সেট যা ইতিমধ্যে পরিদর্শিত শীর্ষগুলির ট্র্যাক রাখে।

আউটপুট:

DFS Traversal starting from vertex 1:
1 2 4 5 3 6 

২. Breadth-First Search (BFS)

BFS (Breadth-First Search) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি শীর্ষ থেকে শুরু করে তার সমস্ত সরাসরি প্রতিবেশী শীর্ষ পরিদর্শন করে, তারপর তাদের প্রতিবেশীদের পরিদর্শন করে এবং এই প্রক্রিয়াটি নোডগুলির স্তরের (level) ভিত্তিতে চলে।

BFS এর বৈশিষ্ট্য:

• Queue-based: BFS সাধারণত Queue ব্যবহার করে বাস্তবায়িত হয়।
• Time Complexity: O(V + E), যেখানে V হল গ্রাফের শীর্ষের সংখ্যা এবং E হল সীমান্তের সংখ্যা।
• Space Complexity: O(V) (Queue এর জন্য)।

উদাহরণ: BFS Traversal using Queue

import java.util.*;

public class GraphBFS {
    private Map<Integer, List<Integer>> adjList;

    public GraphBFS() {
        adjList = new HashMap<>();
    }

    // গ্রাফে একটি সীমান্ত যোগ করা
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // BFS Traversal
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            int v = queue.poll(); // Queue থেকে শীর্ষ বের করা
            System.out.print(v + " ");

            // সমস্ত প্রতিবেশী পরিদর্শন করা
            for (int neighbor : adjList.getOrDefault(v, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        GraphBFS graph = new GraphBFS();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);

        System.out.println("BFS Traversal starting from vertex 1:");
        graph.bfs(1);
    }
}

ব্যাখ্যা:

• addEdge(v, w): গ্রাফের মধ্যে সীমান্ত যোগ করা হয়েছে।
• bfs(start): এটি BFS ট্রাভার্সাল পরিচালনা করে, যেখানে প্রথমে শীর্ষটি start থেকে শুরু হয় এবং পরে queue ব্যবহার করে প্রতিবেশী শীর্ষগুলো পরিদর্শন করা হয়।
• Queue: BFS ট্রাভার্সাল queue ব্যবহার করে, যাতে প্রথমে অ্যাড করা শীর্ষ প্রথমে পরিদর্শন হয়।

আউটপুট:

BFS Traversal starting from vertex 1:
1 2 3 4 5 6 

৩. DFS vs BFS

৪. কোথায় ব্যবহার করবেন?

• DFS (Depth-First Search):
  • Topological Sort: DFS টেকনিক ব্যবহার করে টপোলজিক্যাল সাজানো করতে সাহায্য করে।
  • Cycle Detection: গ্রাফে সাইকেল রয়েছে কিনা তা পরীক্ষা করতে DFS ব্যবহার করা হয়।
  • Pathfinding in Mazes: মেজে বা গ্রাফে পথ অনুসন্ধান করতে DFS ব্যবহৃত হয়।
• BFS (Breadth-First Search):
  • Shortest Path in Unweighted Graph: অযথা ভারী গ্রাফে (যেখানে সমস্ত সীমান্তের ওজন সমান) BFS ব্যবহার করা হয়।
  • Level-order Traversal: গাছের স্তরের মাধ্যমে অনুসন্ধান করতে BFS ব্যবহার হয়।
  • Connectivity Checking: গ্রাফের মধ্যে সংযোগ রয়েছে কিনা তা চেক করার জন্য BFS ব্যবহার করা হয়।

সারাংশ

DFS এবং BFS হল দুটি গুরুত্বপূর্ণ গ্রাফ ট্রাভার্সাল টেকনিক। DFS শীর্ষগুলোকে গভীরভাবে অনুসন্ধান করে, যেখানে BFS স্তরের মাধ্যমে অনুসন্ধান করে। জাভাতে এই দুটি অ্যালগরিদম কাস্টম গ্রাফ ইমপ্লিমেন্টেশন বা java.util লাইব্রেরির সাহায্যে খুব সহজে বাস্তবায়িত করা যায়। DFS এবং BFS এর সঠিক ব্যবহার সমস্যা অনুযায়ী নির্বাচন করতে হয়, এবং এগুলোর ব্যবহার গ্রাফের উপরের স্তর থেকে নিচের স্তরে বা যোগাযোগ পরিমাপ করতে কার্যকরী।

Minimum Spanning Tree (MST) এবং Shortest Path সমস্যা গুলি গ্রাফ তত্ত্বের দুটি অত্যন্ত গুরুত্বপূর্ণ সমস্যা। এই সমস্যাগুলি বিভিন্ন বাস্তব জীবনের সমস্যার সমাধানে ব্যবহৃত হয়, যেমন নেটওয়ার্ক ডিজাইন, রাস্তা নির্মাণ, এবং ট্রাফিক সিস্টেম।

এই টিউটোরিয়ালে আমরা দুটি গুরুত্বপূর্ণ অ্যালগরিদম:

1. Minimum Spanning Tree (MST): Kruskal’s Algorithm এবং Prim’s Algorithm
2. 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:

1. সমস্ত এজ গুলিকে ওজন অনুযায়ী সাজানো হয়।
2. একটি ইউনিয়ন ফাইন্ড ডাটা স্ট্রাকচার ব্যবহার করে প্রতিটি এজ যুক্ত করা হয় যদি এটি সাইকেল তৈরি না করে।

উদাহরণ: 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();
    }
}

ব্যাখ্যা:

1. Union-Find ডাটা স্ট্রাকচার: find() এবং union() ব্যবহার করে সাইকেল চেক করা হয়।
2. 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:

1. প্রাথমিকভাবে একটি সন্নিবিষ্ট ভেরটেক্স নির্বাচন করুন।
2. সন্নিবিষ্ট নোডের সাথেই কম ওজনের এজ সিলেক্ট করুন এবং পরবর্তী নোডে যুক্ত করুন।

উদাহরণ: 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();
    }
}

ব্যাখ্যা:

1. Priority Queue ব্যবহার করে, MST এ প্রতিটি নোডের কম ওজনের এজকে সিলেক্ট করা হয়।
2. 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** গ্রাফে একক সোর্স থেকে সমস্ত গন্তব্যের মধ্যে সবচেয়ে ছোট পথ নির্ধারণ করতে ব্যবহৃত হয়।