# فصل ۰۵ — گراف: مدلِ رابطه، و دو نمایش

<div dir="rtl">

# فصل ۰۵ — گراف: مدلِ رابطه، و دو نمایش

## در این فصل چه یاد می‌گیری

درخت یک قیدِ سفت داشت: هر گره یک پدر، و هیچ حلقه‌ای. **گراف همان درخت است بدونِ آن قید** — هر گره می‌تواند به هر گرهِ دیگری وصل باشد، و مسیرها می‌توانند به خودشان برگردند. جاده‌ها، دوستی‌ها، ارجاعِ صفحه‌ها، وابستگیِ ماژول‌ها: همه گراف‌اند.

ولی این آزادی یک هزینهٔ فوری دارد: **باید تصمیم بگیری یال‌ها را چطور ذخیره کنی.** دو راهِ استاندارد هست و در یک گرافِ ۴٬۰۰۰ گره‌ای یکی `16,261,048` بایت می‌گیرد و دیگری `627,864` بایت. **ولی این یک برندهٔ همیشگی نیست:** از چگالیِ `0.107` به بعد ورق برمی‌گردد و برنده عوض می‌شود.

![شبکه‌ای از گره‌ها با یال‌های متقاطع در کنارِ یک جدولِ مربعیِ خانه‌های پر و خالی](/lesson-assets/t5-s05-graph/prompt/01-image-two-representations.png)

آخر این فصل می‌توانی:

- یک گراف را با فهرستِ مجاورت و با ماتریسِ مجاورت بسازی
- **حافظهٔ هر دو را با عددِ واقعی اندازه بگیری**، نه با حدس
- نقطهٔ سربه‌سرشان را پیدا کنی و بگویی به چه چیزی بند است
- بگویی جهت‌دار و بی‌جهت در کد دقیقاً چه فرقی دارند

## قبل از شروع

**از ترمِ ۲ فصلِ ۸:** `bytearray` وقتی حافظه مهم است. **این فصل ماتریس را با همان می‌سازد** — یک یال یا هست یا نیست، و یک بایت برایش کافی است.

**از ترمِ ۲ فصلِ ۲:** `sys.getsizeof` و اینکه اندازهٔ یک ظرف را از خودِ ظرف بپرسی، نه از حدس.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | حدودِ یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-05-graph.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. کوچک‌ترین نسخهٔ ممکن: فهرستِ مجاورت

شش شهر و شش جاده. **فهرستِ مجاورت** یعنی برای هر گره، فهرستِ گره‌هایی که مستقیماً به آن وصل‌اند.

جاده دوطرفه است، پس هر یال **دو بار** ثبت می‌شود — یک بار در فهرستِ هر سرش. **این همان تفاوتِ بی‌جهت و جهت‌دار است و کلِ فرقش همین دو خط است:** اگر رابطه یک‌طرفه بود (مثلِ «این صفحه به آن صفحه لینک داده»)، فقط یکی از دو خط را می‌نوشتی.

</div>

```python
CITIES = ["ahvaz", "isfahan", "karaj", "mashhad", "shiraz", "tabriz"]
ROADS = [("ahvaz", "isfahan"), ("isfahan", "karaj"), ("isfahan", "shiraz"),
         ("karaj", "tabriz"), ("mashhad", "tabriz"), ("karaj", "mashhad")]

adjacency = {city: [] for city in CITIES}
for a, b in ROADS:
    adjacency[a].append(b)
    adjacency[b].append(a)
for city in adjacency:
    adjacency[city].sort()

for city in CITIES:
    print(f"{city:>8}: {adjacency[city]}")
print("\nتعدادِ گره:", len(CITIES), "· تعدادِ یال:", len(ROADS))
```

```text
   ahvaz: ['isfahan']
 isfahan: ['ahvaz', 'karaj', 'shiraz']
   karaj: ['isfahan', 'mashhad', 'tabriz']
 mashhad: ['karaj', 'tabriz']
  shiraz: ['isfahan']
  tabriz: ['karaj', 'mashhad']

تعدادِ گره: 6 · تعدادِ یال: 6
```

<div dir="rtl">

**خطِ `sort` تزئینی نیست و باید بماند.** ترتیبِ همسایه‌ها در فهرست، ترتیبِ بازدید در فصلِ بعد را تعیین می‌کند؛ اگر مرتبشان نکنی، خروجیِ پیمایشت به ترتیبِ درجِ یال‌ها بند است و **هر بار که فایلِ ورودی‌ات کمی جابه‌جا شود، جوابت هم عوض می‌شود.** این ارزان‌ترین بیمهٔ تکرارپذیری در کلِ این ترم است.

## ۲. همان گراف، نمایشِ دوم: ماتریسِ مجاورت

راهِ دیگر این است که یک جدولِ مربعی بسازی: سطرِ `i` و ستونِ `j`، و در هر خانه یک بیت — یال هست یا نیست. **گره‌ها باید شماره داشته باشند، پس اول یک `dict` می‌سازیم که اسم را به شماره تبدیل کند.**

</div>

```python
index = {city: i for i, city in enumerate(CITIES)}
matrix = [bytearray(len(CITIES)) for _ in CITIES]
for a, b in ROADS:
    matrix[index[a]][index[b]] = 1
    matrix[index[b]][index[a]] = 1

print(f"{'':>8}", " ".join(f"{city[:3]:>3}" for city in CITIES))
for city in CITIES:
    print(f"{city:>8}", " ".join(f"{x:>3}" for x in matrix[index[city]]))
print("\nماتریس متقارن است؟",
      all(matrix[i][j] == matrix[j][i] for i in range(6) for j in range(6)))
print("جادهٔ ahvaz–karaj هست؟", matrix[index['ahvaz']][index['karaj']] == 1,
      "·", "karaj" in adjacency["ahvaz"])
```

```text
         ahv isf kar mas shi tab
   ahvaz   0   1   0   0   0   0
 isfahan   1   0   1   0   1   0
   karaj   0   1   0   1   0   1
 mashhad   0   0   1   0   0   1
  shiraz   0   1   0   0   0   0
  tabriz   0   0   1   1   0   0

ماتریس متقارن است؟ True
جادهٔ ahvaz–karaj هست؟ False · False
```

<div dir="rtl">

**تقارنِ ماتریس، همان بی‌جهت‌بودن است.** در گرافِ جهت‌دار این تقارن از بین می‌رود و ماتریس دیگر آینه ندارد.

و سطرِ آخر یک برتریِ واقعیِ ماتریس را نشان می‌دهد: **پرسشِ «آیا این یال هست؟» در ماتریس یک خواندن است** — سطر و ستون را می‌دانی، خانه را مستقیم می‌خوانی. در فهرستِ مجاورت باید فهرستِ همسایه‌ها را بگردی. **در بخشِ ۵ اندازه‌اش می‌گیریم.**

## ۳. حافظه: `V²` در برابرِ `V + E`

حالا هر دو را بزرگ می‌کنیم. گراف‌های آزمایش **تُنُک**‌اند: به‌ازای هر گره سه یال، که برای شبکه‌های واقعی نسبتِ کاملاً معمولی‌ای است.

> 🌱 **ریشه‌اش کجاست:** حافظهٔ ماتریس با **مربعِ** تعدادِ گره‌ها می‌رود، چون جدولی `V` در `V` است — و «دو برابر شدنِ ضلع، چهار برابر شدنِ مساحت» همان شهودی است که [ریشه ترمِ ۵ فصل ۵](/courses/risheh/lessons/term-5-geometry/session-05-area-perimeter) با مساحت و محیط می‌سازد. **فهرستِ مجاورت اما محیط را می‌شمارد، نه مساحت را:** فقط جفت‌هایی که واقعاً یال‌اند.

> 🤔 **اول حدس بزن:** تعدادِ گره‌ها را دو برابر می‌کنیم و تعدادِ یال‌ها را هم پابه‌پایش. حافظهٔ ماتریس چند برابر می‌شود و حافظهٔ فهرست چند برابر؟ **هر دو عدد را بنویس**، بعد جدول را ببین.

</div>

```python
def make_graph(node_count, edge_count, seed=SEED):
    """گرافِ بی‌جهتِ ساده: بدونِ یالِ تکراری و بدونِ یال از گره به خودش."""
    rng = random.Random(seed)
    edges = set()
    while len(edges) < edge_count:
        a = rng.randrange(node_count)
        b = rng.randrange(node_count)
        if a != b:
            edges.add((min(a, b), max(a, b)))
    graph = {node: [] for node in range(node_count)}
    for a, b in sorted(edges):
        graph[a].append(b)
        graph[b].append(a)
    for node in graph:
        graph[node].sort()          # ترتیبِ ثابت، تا هر اجرا همان نتیجه را بدهد
    return sorted(edges), graph


def list_bytes(graph):
    """حافظهٔ خودِ ظرف‌ها: dict به‌علاوهٔ همهٔ فهرست‌های مجاورت."""
    return sys.getsizeof(graph) + sum(sys.getsizeof(nbrs) for nbrs in graph.values())


def matrix_bytes(node_count):
    """یک بایت به‌ازای هر جفتِ (گره، گره) — یال یا هست یا نیست."""
    rows = [bytearray(node_count) for _ in range(node_count)]
    return sys.getsizeof(rows) + sum(sys.getsizeof(row) for row in rows)


V = [500, 1_000, 2_000, 4_000]
print("تخمینِ حافظهٔ بزرگ‌ترین ماتریس پیش از ساختن:",
      f"{4_000 * 4_000 / 1_000_000:.0f} مگابایت")
sparse = {v: make_graph(v, 3 * v) for v in V}
print("گرافِ ۵۰۰ گره‌ای — درجهٔ گرهِ صفر:", len(sparse[500][1][0]),
      "· سه همسایه‌اش:", sparse[500][1][0][:3])
```

```text
تخمینِ حافظهٔ بزرگ‌ترین ماتریس پیش از ساختن: 16 مگابایت
گرافِ ۵۰۰ گره‌ای — درجهٔ گرهِ صفر: 5 · سه همسایه‌اش: [30, 83, 87]
```

<div dir="rtl">

**آن سطرِ تخمین را قبل از ساختن چاپ کردیم و این عادت اجباری است.** یک ماتریسِ `V` در `V` با یک تایپِ اشتباه می‌تواند از سقفِ حافظهٔ نشست رد شود، و آن‌وقت `MemoryError` نمی‌گیری — **نشستت بدونِ هیچ پیامی ری‌استارت می‌شود.** یک ضرب و تقسیم قبلش، ارزان‌ترین بیمه است.

</div>

```python
print("— ماتریسِ مجاورت")
table([(v, matrix_bytes(v)) for v in V], "بایت", ",d")
print("\n— فهرستِ مجاورت، همان گراف (E = 3V)")
table([(v, list_bytes(sparse[v][1])) for v in V], "بایت", ",d")
```

```text
— ماتریسِ مجاورت
         n              بایت     نسبت به سطر قبل
       500           282,716                   —
     1,000         1,065,856                3.77
     2,000         4,130,184                3.87
     4,000        16,261,048                3.94

— فهرستِ مجاورت، همان گراف (E = 3V)
         n              بایت     نسبت به سطر قبل
       500            78,960                   —
     1,000           157,432                1.99
     2,000           315,856                2.01
     4,000           627,864                1.99
```

<div dir="rtl">

**`3.94` در برابرِ `1.99`.** ستونِ اول رو به `4` می‌رود — یعنی `V²`، دقیقاً همان چیزی که ترمِ ۱ فصلِ ۵ برای «نسبتِ نزدیکِ ۴» گفت. ستونِ دوم `2` است — یعنی خطی، و چون در این گراف‌ها `E = 3V` است، خطی بودن نسبت به `V` و خطی بودن نسبت به `V + E` یک چیزند.

(ستونِ اول از `3.77` شروع می‌شود نه از `4.00`، چون در اندازه‌های کوچک سربارِ ثابتِ هر `bytearray` هنوز سهمِ محسوسی از کل دارد. هرچه `V` بزرگ‌تر می‌شود سهمش کمتر و نسبت به `4` نزدیک‌تر می‌شود.)

**در `V = 4,000` ماتریس بیش از شانزده مگابایت می‌گیرد و فهرست کمتر از ششصد و سی کیلوبایت — بیست و پنج برابر.** و مهم‌تر از خودِ عدد این است که **این نسبت با بزرگ‌تر شدنِ گراف بدتر هم می‌شود**، چون یک ستون با `V` می‌رود و دیگری با `V²`.

## ۴. ولی این برندهٔ همیشگی نیست

جدولِ بالا فقط دربارهٔ گرافِ **تنک** حرف می‌زند. حالا `V` را روی ۵۰۰ ثابت نگه می‌داریم و **تعدادِ یال‌ها را دو برابر می‌کنیم**. حافظهٔ ماتریس به یال‌ها هیچ کاری ندارد و ثابت می‌ماند؛ حافظهٔ فهرست پابه‌پای یال‌ها بالا می‌رود.

> 🤔 **اول حدس بزن:** با `V` ثابت و دو برابر شدنِ `E`، ستونِ نسبتِ حافظهٔ فهرست چه عددی می‌دهد؟ و مهم‌تر: **حدس بزن این دو منحنی در چه چگالی‌ای همدیگر را قطع می‌کنند** — یک‌دهم؟ یک‌سوم؟ نصف؟ عددت را بنویس، بعد جدول را ببین.

</div>

```python
FIXED_V = 500
MAX_EDGES = FIXED_V * (FIXED_V - 1) // 2
DENSE = [7_800, 15_600, 31_200, 62_400]
dense = {e: make_graph(FIXED_V, e) for e in DENSE}

print(f"V = {FIXED_V} · بیشترین یالِ ممکن = {MAX_EDGES:,}"
      f" · حافظهٔ ماتریس = {matrix_bytes(FIXED_V):,} بایت (ثابت)")
print(f"\n{'E':>10}{'چگالی':>10}{'فهرست (بایت)':>18}{'نسبت به سطر قبل':>20}")
previous = None
for e in DENSE:
    size = list_bytes(dense[e][1])
    ratio = "—" if not previous else f"{size / previous:.2f}"
    print(f"{e:>10,}{e / MAX_EDGES:>10.3f}{size:>18,}{ratio:>20}")
    previous = size
```

```text
V = 500 · بیشترین یالِ ممکن = 124,750 · حافظهٔ ماتریس = 282,716 بایت (ثابت)

         E     چگالی      فهرست (بایت)     نسبت به سطر قبل
     7,800     0.063           185,424                   —
    15,600     0.125           318,288                1.72
    31,200     0.250           583,856                1.83
    62,400     0.500         1,117,552                1.91
```

<div dir="rtl">

**سطرِ دوم از عددِ ثابتِ ماتریس رد شده است.** در `E = 7,800` فهرست هنوز برنده است (`185,424` در برابرِ `282,716`)، و در `E = 15,600` باخته (`318,288`). **جایی بینِ این دو، برنده عوض می‌شود.** پیدایش می‌کنیم:

</div>

```python
def crossover(node_count, low, high):
    """کوچک‌ترین تعدادِ یالی که از آن به بعد فهرست از ماتریس سنگین‌تر می‌شود."""
    target = matrix_bytes(node_count)
    while low < high:
        middle = (low + high) // 2
        if list_bytes(make_graph(node_count, middle)[1]) < target:
            low = middle + 1
        else:
            high = middle
    return low


point = crossover(FIXED_V, 1_000, MAX_EDGES)
print(f"نقطهٔ سربه‌سر: {point:,} یال  ·  چگالی {point / MAX_EDGES:.3f}")
print(f"حافظهٔ ماتریس {matrix_bytes(FIXED_V):,} بایت"
      f"  ·  حافظهٔ فهرست در همان نقطه {list_bytes(make_graph(FIXED_V, point)[1]):,} بایت")
```

```text
نقطهٔ سربه‌سر: 13,404 یال  ·  چگالی 0.107
حافظهٔ ماتریس 282,716 بایت  ·  حافظهٔ فهرست در همان نقطه 282,768 بایت
```

<div dir="rtl">

**چگالیِ `0.107`.** یعنی اگر بیش از حدودِ ده درصدِ جفت‌های ممکن واقعاً یال باشند، **ماتریس هم کم‌حافظه‌تر است و هم سریع‌تر.** زیرِ آن، فهرست برنده است — و شبکه‌های واقعی معمولاً خیلی خیلی زیرِ آن‌اند: **همان شبکهٔ فصلِ ۸ چگالیِ `0.00150` دارد.**

**و این دقیقاً همان نقطهٔ تقاطعِ ترمِ ۱ فصلِ ۹ است، فقط این بار محورش زمان نیست، حافظه است.** جملهٔ «فهرستِ مجاورت بهتر است» بدونِ گفتنِ چگالی، همان‌قدر بی‌معناست که یک ادعای پیچیدگی بدونِ بازهٔ `n`.

## ۵. و یک هزینهٔ دیگر که فهرست می‌پردازد

پرسشِ «آیا این یال هست؟» در ماتریس یک خواندن است. در فهرست، **گشتنِ فهرستِ همسایه‌هاست** — و آن فهرست در گرافِ چگال بلند است.

> 🤔 **اول حدس بزن:** با ثابت ماندنِ تعدادِ گره‌ها و دو برابر شدنِ یال‌ها، تعدادِ خانه‌هایی که یک پرسشِ یال می‌خواند چند برابر می‌شود؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
TRIALS = 2_000


def scan_cost(graph):
    """میانگینِ تعدادِ خانه‌ای که «آیا این یال هست؟» در فهرستِ مجاورت می‌خواند."""
    rng = random.Random(SEED)
    total = 0
    for _ in range(TRIALS):
        a = rng.randrange(len(graph))
        b = rng.randrange(len(graph))
        for neighbour in graph[a]:
            total += 1
            if neighbour == b:
                break
    return total / TRIALS


print("— فهرستِ مجاورت: میانگینِ خانه‌های خوانده‌شده در یک پرسشِ یال")
print(f"{'E':>10}{'میانگینِ خانه':>18}{'نسبت به سطر قبل':>20}")
previous = None
for e in DENSE:
    cost = scan_cost(dense[e][1])
    ratio = "—" if not previous else f"{cost / previous:.2f}"
    print(f"{e:>10,}{cost:>18,.1f}{ratio:>20}")
    previous = cost
print("\nهمان پرسش در ماتریس: همیشه یک خواندن، در هر چگالی.")
```

```text
— فهرستِ مجاورت: میانگینِ خانه‌های خوانده‌شده در یک پرسشِ یال
         E     میانگینِ خانه     نسبت به سطر قبل
     7,800              16.4                   —
    15,600              32.1                1.95
    31,200              63.8                1.98
    62,400             126.1                1.98

همان پرسش در ماتریس: همیشه یک خواندن، در هر چگالی.
```

<div dir="rtl">

**ستونِ نسبت `1.98` است: هزینهٔ این پرسش با تعدادِ یال‌ها خطی می‌رود** — چون با ثابت ماندنِ `V`، دو برابر شدنِ یال‌ها یعنی دو برابر شدنِ درجهٔ متوسطِ هر گره. در برابرش، ماتریس در هر چهار سطر همان یک خواندن را دارد.

**پس تصمیم دو محور دارد، نه یکی:** چگالی، و اینکه برنامه‌ات بیشتر «همسایه‌ها را بشمار» می‌پرسد یا «این یالِ مشخص هست؟». **فهرست برای اولی ساخته شده و ماتریس برای دومی.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** دو نمایشِ یک گرافِ واحد، روی دو سؤال: حافظهٔ ظرف‌ها با `sys.getsizeof`، و تعدادِ خانه‌های خوانده‌شده در یک پرسشِ یال. **در کدام بازهٔ `n`؟** ۵۰۰ تا ۴٬۰۰۰ گره با `E = 3V`، و `V = 500` ثابت با ۷٬۸۰۰ تا ۶۲٬۴۰۰ یال. **با چند تکرار، و کمینه یا میانگین؟** حافظه یک اجرا و قطعی؛ پرسشِ یال میانگینِ دو هزار پرسش که — چون با همان `SEED`ِ ساختِ گراف تولید شده‌اند — تقریباً همه‌شان روی **یالِ موجود** می‌افتند. **پس این عدد هزینهٔ جست‌وجوی موفق است، و پرسشِ ناموفق تقریباً دو برابرِ آن خرج دارد چون تا ته فهرست می‌رود.** مرتبه عوض نمی‌شود، عددِ ثابتش عوض می‌شود. **هیچ عددِ ثانیه‌ای در این فصل نیست.**

> ✅ **چک کن:** در `matrix_bytes` به‌جای `bytearray(node_count)` بنویس `[0] * node_count` و جدولِ بخشِ ۳ را دوباره بگیر. **عددهای ماتریس باید حدودِ هشت برابر شوند و ستونِ نسبت همچنان حولِ `4` بماند — این بار حتی نزدیک‌تر به `4` (حدودِ `3.97` به بالا)، چون سربارِ ثابتِ هر سطر حالا سهمِ خیلی کمتری از یک سطرِ سنگین‌تر است.** یعنی نقطهٔ سربه‌سر جابه‌جا می‌شود ولی مرتبه نه — **همان تفکیکِ ثابت و مرتبه که کلِ ترمِ ۱ دربارهٔ آن بود.**

> 🔧 **اگر کار نکرد:** رایج‌ترین خطای کار با فهرستِ مجاورت این است که سراغِ گره‌ای بروی که اصلاً در گراف نیست — یک غلطِ املایی در نامِ گره کافی است:

</div>

```python
try:
    print(adjacency["yazd"])
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
print("همسایه‌های یک گرهِ ناشناس، بدونِ خطا:", adjacency.get("yazd", []))
```

```text
KeyError: 'yazd'
همسایه‌های یک گرهِ ناشناس، بدونِ خطا: []
```

<div dir="rtl">

**و سطرِ دوم را با احتیاط به‌کار ببر.** `.get(node, [])` خطا را خفه می‌کند و برای پیمایشی که ممکن است به گرهِ بی‌همسایه برسد مناسب است — **ولی اگر گره واقعاً وجود نداشته باشد، به تو می‌گوید «همسایه ندارد» به‌جای «چنین گره‌ای نیست».** دو جوابِ کاملاً متفاوت، با یک ظاهر. اگر پیمایشت ساکت شد و هیچ گره‌ای پیدا نکرد، اول همین را چک کن.

> 🤖 **از دستیارت بپرس:** «برای یک شبکهٔ اجتماعی با میلیون‌ها کاربر، فهرستِ مجاورت بهتر است یا ماتریس؟» بعد **جدولِ بخشِ ۴ را جلویش بگذار و بپرس:** «جوابت به چگالی بند است یا نه؟» — جوابِ درست باید عددِ چگالی را بخواهد، نه فقط تعدادِ کاربرها.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| graph | گراف | مجموعه‌ای از گره‌ها و یال‌هایی که آن‌ها را به هم وصل می‌کنند |
| edge | اِج | یال: یک رابطه بینِ دو گره |
| degree | دِگری | درجهٔ یک گره: تعدادِ یال‌هایی که به آن وصل‌اند |
| adjacency list | اَجِیسِنسی لیست | فهرستِ مجاورت: برای هر گره، فهرستِ همسایه‌هایش |
| adjacency matrix | اَجِیسِنسی ماتریکس | ماتریسِ مجاورت: جدولی `V` در `V` از بودن یا نبودنِ یال |
| density | دنسیتی | چگالی: نسبتِ یال‌های موجود به همهٔ یال‌های ممکن |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا حافظهٔ ماتریسِ مجاورت به تعدادِ یال‌ها هیچ ربطی ندارد؟

**تمرینِ اجباری:** همان گرافِ شش‌شهری را **جهت‌دار** بساز — فقط یکی از دو خطِ درج را نگه دار — و هر دو نمایش را دوباره چاپ کن. **سؤالِ اصلی: مجموعِ طولِ فهرست‌های مجاورت چه می‌شود و چرا؟** بعد `list_bytes` را برای هر دو نسخه بگیر و بگو **صرفه‌جوییِ حافظه دقیقاً چند برابر است و آیا برای ماتریس هم همین‌قدر است.**

**تمرینِ ستاره‌دار ⭐:** نقطهٔ سربه‌سر را برای `V = 250`، `500`، `1,000` و `2,000` پیدا کن و **چگالیِ** آن نقطه را در یک جدول کنارِ هم بگذار. **قبل از اجرا پیش‌بینی کن** چگالیِ سربه‌سر با بزرگ‌تر شدنِ `V` بالا می‌رود، پایین می‌آید، یا ثابت می‌ماند — و **دلیلت را از فرمولِ حافظهٔ دو ساختار دربیاور، نه از حدس**. حالا اندازه بگیر و خطای پیش‌بینی‌ات را بنویس.

## در فصل بعد

حالا گراف را داریم و هنوز هیچ کاری با آن نکرده‌ایم. **فصلِ بعد دو پیمایشِ فصلِ ۲ را روی گراف می‌برد** — همان `queue` و همان `stack` — و می‌بینی که یکی از این دو کوتاه‌ترین مسیر را می‌دهد و دیگری نمی‌دهد.

آن‌جا کدی می‌بینی که با **یک کلمه** تفاوت، به‌جای فاصلهٔ `[0, 1, 3, 2, 3, 3, 2, 1]` جوابِ `[0, 1, 6, 5, 4, 3, 2, 1]` می‌دهد — **بدونِ هیچ خطایی، و با دیدنِ هر هشت گره.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s05-graph (یادستان, Yaadestan)
