Topic 01 · Graph
Graph Basics — Adjacency Matrix ও Adjacency List
Graph এর ভাষাটা আগে শিখতে হবে। BFS, DFS, Topological Sort, Dijkstra — এই চারটার
ভিত্তি এই এক পাতাতেই। Graph কীভাবে খাতায় লিখবে, সেটাই এখানকার মূল প্রশ্ন।
Exam Chance ≈ 60%
★★
সময় ≈ ৮ মিনিট
পরের ৪টা টপিকের ভিত্তি
১. প্রশ্ন (Question)
EXAM QUESTION
নিচের undirected graph টির জন্য Adjacency Matrix এবং Adjacency List তৈরি করো।
প্রতিটি vertex এর degree বের করো এবং দেখাও যে সব degree এর যোগফল = 2 × (edge সংখ্যা)।
V = { A, B, C, D, E, F }
E = { A–B, A–C, B–D, B–E, C–F, E–F }
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ Graph কী?
Graph হলো কিছু বিন্দু (vertex বা node) আর সেই বিন্দুগুলোর মধ্যে টানা কিছু রেখা
(edge) নিয়ে তৈরি একটা structure। গাণিতিকভাবে লেখা হয় G = (V, E) — যেখানে
V হলো vertex এর সেট আর E হলো edge এর সেট।
কেন দরকার: বাস্তবের প্রায় সব সম্পর্ককেই graph দিয়ে দেখানো যায় — শহরের রাস্তা,
Facebook এর বন্ধু তালিকা, কোর্সের prerequisite। তাই algorithm পড়ার আগে graph লেখার
ভাষাটা জানা লাগবেই।
২.২ Directed বনাম Undirected Graph
Undirected graph: edge এর কোনো দিক নেই। A–B মানে A থেকে B যাওয়া যায়, আবার B থেকে A ও যাওয়া যায়।
Directed graph (digraph): edge এর দিক আছে। A→B মানে শুধু A থেকে B যাওয়া যাবে, উল্টো দিকে নয়।
কেন দরকার: এই একটা পার্থক্যেই matrix সম্পূর্ণ বদলে যায় — undirected হলে matrix
symmetric হয় (উপরের ত্রিভুজ আর নিচের ত্রিভুজ একই), directed হলে সাধারণত হয় না।
পরীক্ষায় প্রথমেই দেখতে হবে graph টা কোন ধরনের।
২.৩ Weighted Graph
প্রতিটি edge এর সাথে একটা সংখ্যা (cost / distance / weight) লেগে থাকলে সেটা
weighted graph। যেমন A→B এর weight 4 মানে A থেকে B যেতে খরচ 4।
কেন দরকার: BFS/DFS এ weight লাগে না, কিন্তু Dijkstra পুরোপুরি weight এর উপর
চলে। Weighted graph এর matrix এ 1 এর বদলে weight বসে, আর edge না থাকলে
∞ বসে (0 নয়!)।
২.৪ Degree, In-degree, Out-degree
Degree = একটা vertex এ কয়টা edge লেগে আছে।
Directed graph এ দুই ভাগ —
•
In-degree = কয়টা edge ভেতরে ঢুকছে
•
Out-degree = কয়টা edge বাইরে যাচ্ছে
কেন দরকার: Kahn's Algorithm পুরোটাই in-degree এর
উপর দাঁড়ানো — in-degree 0 মানে ওই কাজটা এখনই করা যায়। তাই এই সংজ্ঞাটা মুখস্থ থাকতে হবে।
২.৫ Path ও Cycle
Path = পরপর কিছু vertex, যাদের প্রতি জোড়ার মাঝে edge আছে। যেমন A → C → F।
Cycle = এমন path যা যেখান থেকে শুরু, সেখানেই শেষ হয় (X → Y → Z → X)।
কেন দরকার: Cycle থাকলে
Topological Sort করা
যায় না — এই এক লাইনের জন্যই cycle এর সংজ্ঞা লাগে।
২.৬ Adjacency — শব্দটার মানে
দুইটা vertex এর মাঝে সরাসরি edge থাকলে তাদের adjacent (পাশাপাশি / প্রতিবেশী) বলে।
তাই Adjacency Matrix মানে "কে কার প্রতিবেশী" — সেটা একটা টেবিলে লেখা।
৩. Exam Definition (English)
Graph: A graph G = (V, E) is a non-linear data structure consisting of a
finite set of vertices V and a set of edges E, where each edge connects
a pair of vertices.
Adjacency Matrix: An adjacency matrix is a V × V two-dimensional array in
which the entry M[i][j] = 1 if there is an edge from vertex i to vertex
j, and 0 otherwise. For a weighted graph the entry stores the weight of
the edge instead of 1. It requires O(V²) space.
Adjacency List: An adjacency list represents a graph as an array of lists, where the list
at index i contains all vertices adjacent to vertex i. It requires
O(V + E) space.
৪. Concept Explanation (বাংলায়)
Graph কে কম্পিউটারে বা খাতায় রাখার দুইটা প্রধান উপায় আছে — Matrix আর List।
Matrix হলো একটা চারকোনা ছক। সারি (row) মানে "কোথা থেকে", কলাম (column) মানে "কোথায়"।
A থেকে B তে edge থাকলে A সারি ও B কলামের ঘরে 1 লিখি, না থাকলে 0। এতে "A আর B এর মাঝে
edge আছে কি?" — এই প্রশ্নের উত্তর এক ধাপেই (O(1)) পাওয়া যায়। কিন্তু জায়গা লাগে
V × V, তাই edge কম থাকলেও পুরো ছক ভরে রাখতে হয় — অপচয়।
List হলো প্রতিটি vertex এর পাশে তার প্রতিবেশীদের নাম লিখে রাখা। যেমন
B → A, D, E। এতে জায়গা লাগে শুধু যতটুকু edge আছে ততটুকু। কোনো node এর
"সব প্রতিবেশী দেখাও" — এই কাজটা list এ অনেক দ্রুত, তাই BFS/DFS এর complexity list এ
O(V + E) হয়, কিন্তু matrix এ O(V²) হয়ে যায়।
৫. Rules — খাতায় কীভাবে লিখবে
Adjacency Matrix বানানোর নিয়ম
- সব vertex কে একটা নির্দিষ্ট ক্রমে সাজাও (সাধারণত alphabetical / numerical)। একই ক্রম সারি ও কলাম দুই জায়গায়।
- শুরুতে সব ঘরে 0 বসাও।
- প্রতিটি edge
u–v এর জন্য M[u][v] = 1 লিখো।
- Undirected হলে সাথে সাথে
M[v][u] = 1 ও লিখো (দুই দিকেই)।
- Weighted হলে 1 এর বদলে weight বসাও; edge না থাকলে
∞ (বা 0, তবে কোনটা ব্যবহার করছ লিখে দাও)।
- Self-loop না থাকলে diagonal (M[A][A], M[B][B] …) সব 0 থাকবে।
কেন এই ক্রম: ক্রম না লিখলে examiner বুঝবে না কোন সারি কোন vertex এর।
খাতায় সারি ও কলামের মাথায় অবশ্যই vertex এর নাম লিখে দিতে হবে।
Adjacency List বানানোর নিয়ম
- প্রতিটি vertex এর জন্য একটা লাইন নাও।
- ওই vertex থেকে যাদের কাছে সরাসরি যাওয়া যায়, তাদের নাম ক্রম অনুযায়ী লিখো।
- Undirected হলে প্রতিটি edge দুইবার আসবে — একবার u এর লাইনে, একবার v এর লাইনে।
- Weighted হলে পাশে weight লিখো:
B → A(4), D(5)
কেন ক্রম অনুযায়ী: BFS/DFS এর উত্তর প্রতিবেশীর ক্রমের উপর নির্ভর করে।
List টা alphabetical রাখলে পরে traversal এর উত্তরও নির্দিষ্ট হয়।
৬. ধাপে ধাপে ব্যাখ্যা
ধাপ ১ — Graph টা কোন ধরনের সেটা ঠিক করো
Edge গুলো
A–B এভাবে লেখা (তীর নেই) মানে
undirected। কোনো সংখ্যা নেই মানে
unweighted।
কেন দরকার: undirected বলেই matrix symmetric হবে এবং list এ প্রতিটি edge দুইবার লিখতে হবে।
ধাপ ২ — 6 × 6 খালি ছক আঁকো
সারি ও কলাম দুই জায়গায় A, B, C, D, E, F ক্রমে লিখে সব ঘরে 0 বসাও।
কেন দরকার: আগে থেকে 0 বসিয়ে নিলে পরে শুধু 1 বসানোর কাজ থাকে — ভুল হওয়ার সুযোগ কমে।
ধাপ ৩ — একটা একটা করে edge বসাও (দুই দিকে)
A–B → M[A][B] = 1 এবং M[B][A] = 1। এভাবে ছয়টা edge শেষ করো।
কেন দুই দিকে: undirected এ A থেকে B আর B থেকে A — দুইটাই বৈধ চলাচল, তাই দুই ঘরেই 1।
ধাপ ৪ — Degree গুনে যাচাই করো
প্রতিটি সারির 1 গুলো যোগ করলেই ওই vertex এর degree। শেষে সব degree যোগ করে দেখো
সেটা
2 × E এর সমান হয় কিনা।
কেন দরকার: এটা free verification। মিল না হলে বুঝবে কোথাও একটা edge বসাতে ভুলে গেছ।
৭. ASCII Diagram
A
/ \
B C
/ \ \
D E ————— F
Undirected graph · 6 vertex, 6 edge · E আর F এর মাঝেও একটা edge আছে
৮. প্রশ্নের সমাধান — ধাপে ধাপে
Step 1 — Adjacency Matrix
কী করলাম: ছয়টা edge এর প্রতিটার জন্য দুইটা করে ঘরে 1 বসালাম।
কেন করলাম: graph টা undirected, তাই সম্পর্কটা দুই দিকেই সত্য।
যাচাই: matrix টা diagonal বরাবর ভাঁজ করলে দুই পাশ হুবহু মিলে যাচ্ছে — অর্থাৎ symmetric ✓
Step 2 — Adjacency List
A → B , C
B → A , D , E
C → A , F
D → B
E → B , F
F → C , E
কী করলাম: প্রতিটি vertex এর প্রতিবেশীদের alphabetical ক্রমে লিখলাম।
কেন করলাম: BFS/DFS এ এই ক্রমটাই উত্তর ঠিক করে দেয়।
খেয়াল করো: মোট নাম লেখা হয়েছে 2 + 3 + 2 + 1 + 2 + 2 = 12 টা = 2 × 6 edge ✓
Step 3 — Degree যাচাই
| Vertex | A | B | C | D | E | F | যোগফল |
|---|
| Degree | 2 | 3 | 2 | 1 | 2 | 2 | 12 |
|---|
Handshaking Lemma অনুযায়ী Σ degree = 2 × E → 12 = 2 × 6 ✓
অর্থাৎ কোনো edge বাদ পড়েনি বা দুইবার বসেনি।
Step 4 — বোনাস: Weighted Directed উদাহরণ
যদি প্রশ্নে directed weighted graph দেয়, যেমন
A→B = 4, A→C = 1, C→B = 2, B→D = 5, C→D = 8, D→E = 3 — তখন matrix হবে:
এখানে matrix
symmetric নয় — কারণ graph টা directed। M[A][B] = 4 কিন্তু M[B][A] = ∞,
অর্থাৎ B থেকে A তে ফেরা যায় না। এই matrix টাই
Dijkstra এর প্রশ্নে ব্যবহার হবে।
৯. Final Exam Answer (English)
Adjacency Matrix (symmetric, undirected):
A B C D E F
A [ 0 1 1 0 0 0 ]
B [ 1 0 0 1 1 0 ]
C [ 1 0 0 0 0 1 ]
D [ 0 1 0 0 0 0 ]
E [ 0 1 0 0 0 1 ]
F [ 0 0 1 0 1 0 ]
Adjacency List: A→B,C · B→A,D,E · C→A,F · D→B · E→B,F · F→C,E
Σ degree = 12 = 2 × 6 edges ✓ · Space: matrix O(V²), list O(V + E)
Matrix বনাম List — তুলনা (theory question এ আসে)
| বিষয় | Adjacency Matrix | Adjacency List |
|---|
| Space | O(V²) | O(V + E) |
| "u–v edge আছে?" যাচাই | O(1) | O(degree) |
| সব প্রতিবেশী বের করা | O(V) | O(degree) |
| Edge যোগ করা | O(1) | O(1) |
| কখন ভালো | Dense graph (edge বেশি) | Sparse graph (edge কম) |
| BFS / DFS complexity | O(V²) | O(V + E) |
১০. Common Mistakes
- Undirected এ এক দিকে 1 বসানো — সবচেয়ে বেশি হওয়া ভুল। দুই ঘরেই বসাতে হবে, matrix অবশ্যই symmetric হবে।
- Directed এ দুই দিকে 1 বসানো — উল্টো ভুল। তীর যেদিকে, শুধু সেদিকেই।
- সারি-কলামের নাম না লেখা — শুধু সংখ্যার ছক দিলে examiner মেলাতে পারবে না, নম্বর কাটবে।
- Weighted graph এ edge না থাকলে 0 বসানো — 0 মানে "খরচ শূন্য", অর্থাৎ ফ্রিতে যাওয়া যায়! সেখানে
∞ লিখতে হবে।
- Diagonal এ 1 বসানো — self-loop না থাকলে M[A][A] সবসময় 0।
- List এ প্রতিবেশীর ক্রম এলোমেলো করা — পরে BFS/DFS এর উত্তর বদলে যাবে।
- Degree যাচাই না করা — এক লাইনের কাজ, কিন্তু ভুল ধরিয়ে দেয়।
১১. Viva Questions
Q: Adjacency Matrix আর Adjacency List — কোনটা কখন ব্যবহার করবে এবং কেন?
Q: Undirected graph এর adjacency matrix সবসময় symmetric হয় কেন?
Q: Handshaking Lemma কী? Σ degree = 2E হয় কেন?
Q: Weighted graph এ edge না থাকলে matrix এ কী বসাবে এবং কেন 0 নয়?
Q: In-degree ও Out-degree এর পার্থক্য কী? কোন algorithm এ in-degree লাগে?
Q: V টা vertex এর একটা undirected simple graph এ সর্বোচ্চ কয়টা edge থাকতে পারে? (উত্তর: V(V−1)/2)
Q: Adjacency matrix ব্যবহার করলে BFS এর complexity O(V²) হয় কেন?
১২. Practice Questions
- Directed graph
1→2, 1→3, 2→4, 3→4, 4→5 এর adjacency matrix ও list লেখো এবং প্রতিটি node এর in-degree ও out-degree বের করো।
উত্তর দেখাও
List: 1→2,3 · 2→4 · 3→4 · 4→5 · 5→(নেই)
In-degree: 1=0, 2=1, 3=1, 4=2, 5=1 · Out-degree: 1=2, 2=1, 3=1, 4=1, 5=0
Matrix symmetric হবে না, কারণ graph টা directed।
- একটা undirected graph এ 5 টা vertex আর প্রতিটির degree 4 — মোট কয়টা edge?
উত্তর দেখাও
Σ degree = 5 × 4 = 20 → E = 20 / 2 = 10 টা edge (এটাই complete graph K₅)।
- Weighted undirected graph
A–B(3), A–C(5), B–C(1), C–D(7) এর matrix আঁকো। কোন ঘরে ∞ বসবে?
উত্তর দেখাও
A–D আর B–D এর মাঝে কোনো edge নেই, তাই M[A][D] = M[D][A] = ∞ এবং M[B][D] = M[D][B] = ∞। বাকি সব ঘরে weight, diagonal এ 0।
- একই graph এর জন্য matrix ও list — কোনটাতে কম জায়গা লাগবে যদি V = 1000 আর E = 2000 হয়? হিসাব করে দেখাও।
উত্তর দেখাও
Matrix: 1000² = 10,00,000 ঘর। List: V + 2E = 1000 + 4000 = 5000 entry। অর্থাৎ list প্রায় 200 গুণ কম জায়গা নেবে — কারণ graph টা sparse।
- Adjacency matrix দেওয়া থাকলে কীভাবে বুঝবে graph টা directed না undirected? ব্যাখ্যা করো।
- Self-loop আর parallel edge কী? Adjacency matrix এ এগুলো কীভাবে দেখাবে?
- নিচের list থেকে graph টা আঁকো এবং edge সংখ্যা বের করো:
P→Q,R · Q→R,S · R→S · S→P