Graph (গ্রাফ) একটি ডেটা স্ট্রাকচার যা এক বা একাধিক নোড (nodes) এবং তাদের মধ্যে থাকা এজ (edges) এর মাধ্যমে সম্পর্ক বা সংযোগ দেখায়। এটি একটি শক্তিশালী গঠন যা জটিল সম্পর্কযুক্ত তথ্যের মডেলিং এবং বিশ্লেষণে ব্যবহৃত হয়। গ্রাফের মাধ্যমে বিভিন্ন বাস্তব জীবনের সমস্যা যেমন রুট নির্ধারণ (routing), নেটওয়ার্ক অ্যানালিসিস, সোশ্যাল নেটওয়ার্ক সম্পর্ক ইত্যাদি মডেল করা যায়।
Graph এর ধারণা
গ্রাফে দুটি মৌলিক উপাদান থাকে:
- Nodes (নোড): একে ভেরটিস (vertices)ও বলা হয়। এটি গ্রাফের মূল উপাদান, যার মধ্যে একটি ইউনিক আইডেন্টিফায়ার থাকে। একটি নোড গ্রাফের তথ্য ধারণ করে।
- Edges (এজ): এটি দুটি নোডের মধ্যে সম্পর্ক বা সংযোগ নির্দেশ করে। একটি এজ নোডগুলোকে সংযুক্ত করে এবং তাদের মধ্যে যোগাযোগের পথ তৈরি করে।
গ্রাফে নোডের সংখ্যা সাধারণত V (vertices) এবং এজের সংখ্যা E (edges) দ্বারা চিহ্নিত করা হয়।
Graph এর প্রকারভেদ
গ্রাফ দুটি প্রধান প্রকারে বিভক্ত হতে পারে:
- Directed Graph (ডাইরেক্টেড গ্রাফ): যেখানে এজগুলোর একটি নির্দিষ্ট দিক থাকে, অর্থাৎ এক নোড থেকে অন্য নোডে যাওয়ার জন্য একটি নির্দিষ্ট দিক থাকে।
- 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 (গ্রাফ) হল একটি ডেটা স্ট্রাকচার যা নোড এবং তাদের মধ্যে সংযোগ (এজ) ব্যবহার করে সম্পর্ক নির্ধারণ করে। গ্রাফ দুটি প্রধান প্রকারের হতে পারে:
- Directed Graph (ডাইরেক্টেড গ্রাফ): যেখানে প্রতিটি এজের একটি নির্দিষ্ট দিক থাকে। এটি সাধারণত সোশ্যাল নেটওয়ার্ক, ওয়েব লিঙ্ক ইত্যাদিতে ব্যবহৃত হয়।
- Undirected Graph (আন্ডাইরেক্টেড গ্রাফ): যেখানে এজের কোনো দিক থাকে না, অর্থাৎ প্রতিটি সম্পর্ক উভয়দিকী। এটি বন্ধু সম্পর্ক বা সাধারণ সংযোগের ক্ষেত্রে ব্যবহৃত হয়।
এ দুটি গ্রাফের প্রকার বিভিন্ন ধরনের বাস্তব জীবনের সম্পর্ক এবং সমস্যার সমাধানে ব্যবহৃত হয়।
Read more
