Graph (গ্রাফ) কী?
Graph হলো Vertex (নোড) এবং Edge (সংযোগ) এর সমষ্টি। প্রতিটি Vertex অন্য Vertex-এর সাথে Edge দ্বারা সংযুক্ত।
ধরনসমূহ
- Undirected Graph — Edge-এর কোনো দিক নেই (দুদিকেই যাওয়া যায়)
- Directed Graph (Digraph) — Edge-এর একটি নির্দিষ্ট দিক আছে
- Weighted Graph — Edge-এ weight/cost আছে (যেমন দূরত্ব)
- Cyclic — চক্র আছে; Acyclic — চক্র নেই
Graph-র রিপ্রেজেন্টেশন
# Adjacency List (সবচেয়ে জনপ্রিয়)
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"]
}
Graph Traversal
- BFS (Breadth-First Search) — স্তরে স্তরে খোঁজে (Queue ব্যবহার করে)
- DFS (Depth-First Search) — গভীরে গিয়ে খোঁজে (Stack ব্যবহার করে)
ব্যবহার
- Google Maps — শহর = Vertex, রাস্তা = Edge, দূরত্ব = Weight
- Facebook/Instagram — ব্যবহারকারী = Vertex, বন্ধুত্ব = Edge
- Internet — Router = Vertex, Cable = Edge