গ্রাফ কীভাবে উপস্থাপন করেন: সন্নিহিত তালিকা বনাম সন্নিহিত ম্যাট্রিক্স?

Question

Accepted Answer

**গ্রাফ** হল **শীর্ষবিন্দু**র একটি সমূহ যা **প্রান্ত** দ্বারা সংযুক্ত। দুটি মান প্রতিনিধিত্ব হল **সন্নিহিত তালিকা** (প্রতিটি শীর্ষবিন্দু এর প্রতিবেশীদের সংরক্ষণ করে) এবং **সন্নিহিত ম্যাট্রিক্স** (বুলিয়ান মানের V×V গ্রিড)। পছন্দ গ্রাফের **ঘনত্ব**র উপর নির্ভর করে।

## দুটি ফর্ম

```text
Graph:  0 - 1
        |   |
        2 - 3

Adjacency list:          Adjacency matrix:
0: [1, 2]                    0 1 2 3
1: [0, 3]                 0 [0 1 1 0]
2: [0, 3]                 1 [1 0 0 1]
3: [1, 2]                 2 [1 0 0 1]
                          3 [0 1 1 0]
```

## কোড

```python
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1]            # O(1) to get a vertex's neighbors

# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1  # O(1) edge lookup
```

## তুলনা (V শীর্ষবিন্দু, E প্রান্ত)

| | সন্নিহিত তালিকা | সন্নিহিত ম্যাট্রিক্স |
|---|---|---|
| স্থান | O(V + E) | O(V²) |
| প্রান্ত বিদ্যমান? | O(degree) | O(1) |
| প্রতিবেশীদের পুনরাবৃত্তি করুন | O(degree) | O(V) |
| সর্বোত্তম | বিরল গ্রাফের জন্য | ঘন গ্রাফের জন্য |

## কেন এটি গুরুত্বপূর্ণ

বেশিরভাগ বাস্তব-বিশ্ব গ্রাফ (সামাজিক নেটওয়ার্ক, রোড ম্যাপ, নির্ভরতা গ্রাফ) **বিরল**, তাই সন্নিহিত তালিকাগুলি বিশাল স্থান সাশ্রয় করে এবং BFS/DFS এর মতো ট্রাভার্সালগুলি গতিশীল করে।

ট্রেড-অফ জেনে রাখা আপনাকে এমন প্রতিনিধিত্ব বেছে নিতে দেয় যা আপনার গ্রাফ অ্যালগরিদমগুলি দক্ষ রাখে, বাংসংক্ষেপে O(V²) মেমরি ব্যবহার করা এড়ায়।

	সন্নিহিত তালিকা	সন্নিহিত ম্যাট্রিক্স
স্থান	O(V + E)	O(V²)
প্রান্ত বিদ্যমান?	O(degree)	O(1)
প্রতিবেশীদের পুনরাবৃত্তি করুন	O(degree)	O(V)
সর্বোত্তম	বিরল গ্রাফের জন্য	ঘন গ্রাফের জন্য