الدرس 17 · الوحدة 7: اختيار تركيب بيانات لحل مشكلة
الرسوم البيانية وتمثيلها
الخرائط والشبكات الاجتماعية والإنترنت: كلها عقد وأضلاع. ⏱ نحو 35 دقيقة.
بعد هذا الدرس ستستطيع أن:
- تعرّف الرسم البياني ومصطلحاته: العقدة والضلع والدرجة والمسار.
- تميّز الرسم الموجّه وغير الموجّه والموزون.
- تمثّل الرسم بقائمة الجوار وبمصفوفة الجوار.
- تختار التمثيل المناسب حسب كثافة الرسم.
١عقد وأضلاع
الرسم البياني Graph: مجموعة عقد Vertices، وبينها أضلاع Edges. المدن والطرق، والأشخاص والصداقات، وصفحات الويب والروابط بينها: كلها رسوم بيانية.
| المصطلح | معناه | مثال |
|---|---|---|
| غير موجّه Undirected | الضلع في الاتجاهين. | طريق بين مدينتين |
| موجّه Directed | الضلع في اتجاه واحد. | المتابعة في تويتر، والشارع ذو الاتجاه الواحد |
| موزون Weighted | لكل ضلع وزن. | المسافة أو الزمن أو التكلفة |
| الجيران Neighbors | العقد المتصلة بعقدة مباشرة. | جيران جدة: رابغ ومكة |
| الدرجة Degree | عدد أضلاع العقدة. | درجة بدر: 3 |
| المسار Path | سلسلة أضلاع من عقدة إلى أخرى. | المدينة ← بدر ← رابغ ← جدة |
٢التمثيل الأول: قائمة الجوار
لكل عقدة قائمة بجيرانها. نستخدم قاموسًا: العقدة ← قائمة (الجار، الوزن). هذا التمثيل الأشهر؛ لأنه يحفظ الأضلاع الموجودة فقط:
roads = [("المدينة", "ينبع", 230), ("المدينة", "بدر", 150), ("ينبع", "رابغ", 180), ("بدر", "رابغ", 120), ("رابغ", "جدة", 150), ("جدة", "مكة", 80), ("مكة", "الطائف", 90), ("بدر", "مكة", 330)] graph = {}for a, b, km in roads: graph.setdefault(a, []).append((b, km)) graph.setdefault(b, []).append((a, km)) # غير موجّه: في الاتجاهين print("جيران بدر:", graph["بدر"])print("درجة رابغ:", len(graph["رابغ"]))print("عدد المدن:", len(graph), "| عدد الطرق:", sum(len(v) for v in graph.values()) // 2)
>>> %Run main.py
جيران بدر: [('المدينة', 150), ('رابغ', 120), ('مكة', 330)]
درجة رابغ: 3
عدد المدن: 7 | عدد الطرق: 8
>>>
٣التمثيل الثاني: مصفوفة الجوار
جدول n × n: الخلية [i][j] فيها وزن الضلع بين العقدتين، أو 0 إن لم يوجد. سؤال «هل يوجد طريق بين المدينتين؟» إجابته O(1)، لكن الجدول يحجز O(n²) ذاكرة ولو كانت الطرق قليلة:
cities = ["المدينة", "ينبع", "بدر", "رابغ"]idx = {c: i for i, c in enumerate(cities)}n = len(cities)matrix = [[0] * n for _ in range(n)] for a, b, km in [("المدينة", "ينبع", 230), ("المدينة", "بدر", 150), ("ينبع", "رابغ", 180), ("بدر", "رابغ", 120)]: matrix[idx[a]][idx[b]] = km matrix[idx[b]][idx[a]] = km for c, row in zip(cities, matrix): print(f"{c:>8}", row)print("المدينة ← رابغ مباشرة؟", matrix[idx["المدينة"]][idx["رابغ"]] > 0)
>>> %Run main.py
المدينة [0, 230, 150, 0]
ينبع [230, 0, 0, 180]
بدر [150, 0, 0, 120]
رابغ [0, 180, 120, 0]
المدينة ← رابغ مباشرة؟ False
>>>
٤أيّ التمثيلين؟
| قائمة الجوار | مصفوفة الجوار | |
|---|---|---|
| الذاكرة | O(V + E) | O(V²) |
| هل يوجد ضلع بين a و b؟ | O(درجة a) | O(1) |
| المرور على جيران عقدة | O(درجتها) | O(V) |
| يناسب | الرسوم المتفرقة: الطرق، والشبكات الاجتماعية | الرسوم الكثيفة الصغيرة: جدول مسافات بين 20 مدينة |
V عدد العقد و E عدد الأضلاع. في شبكة اجتماعية من مليار شخص، لكل شخص بضع مئات من الأصدقاء: المصفوفة تحتاج مليار × مليار خانة (مستحيل)، وقائمة الجوار تحتاج بقدر الصداقات فقط.
٥رسم موجّه
# من يتابع من؟ (الضلع في اتجاه واحد)follows = { "سارة": ["نورة", "ريم"], "نورة": ["سارة"], "ريم": [], "هند": ["سارة", "ريم"],}followers = {p: [] for p in follows}for p, targets in follows.items(): for t in targets: followers[t].append(p) for p in follows: print(p, "| يتابع:", len(follows[p]), "| متابعوه:", followers[p])
>>> %Run main.py
سارة | يتابع: 2 | متابعوه: ['نورة', 'هند']
نورة | يتابع: 1 | متابعوه: ['سارة']
ريم | يتابع: 0 | متابعوه: ['سارة', 'هند']
هند | يتابع: 2 | متابعوه: []
>>>
توقّع وتحقّق
علاقة المتابعة في وسائل التواصل:
اتجاه واحد.
مصفوفة الجوار تحتاج ذاكرة:
جدول
V × V.أنسب تمثيل لشبكة اجتماعية ضخمة:
متفرقة.
عدد أضلاع العقدة يسمى:
Degree.الخلاصة
- الرسم: عقد وأضلاع، قد تكون موجّهة أو موزونة.
- قائمة الجوار: قاموس العقدة ← جيرانها، ذاكرتها
O(V + E). - مصفوفة الجوار: جدول
V × V، فحص الضلعO(1)وذاكرتهاO(V²). - المتفرق ← قائمة الجوار، والكثيف الصغير ← المصفوفة.
تحدٍّ برمجي: أقرب جار لكل مدينة
متوسطابنِ قائمة الجوار للخريطة، ثم اطبع لكل مدينة أقرب مدينة مجاورة لها والمسافة، بترتيب أبجدي للمدن.
المطلوب:
- ابنِ graph بقاموس كما في الدرس.
- لكل مدينة: الجار ذو أقل مسافة (min مع key).
- اطبع: المدينة ← الجار (المسافة)، مثل: الطائف ← مكة
(90)
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
roads = [("المدينة", "ينبع", 230), ("المدينة", "بدر", 150), ("ينبع", "رابغ", 180), ("بدر", "رابغ", 120), ("رابغ", "جدة", 150), ("جدة", "مكة", 80), ("مكة", "الطائف", 90), ("بدر", "مكة", 330)]
الطائف ← مكة (90)
المدينة ← بدر (150)
بدر ← رابغ (120)
جدة ← مكة (80)
رابغ ← بدر (120)
مكة ← جدة (80)
ينبع ← رابغ (180)
💡 تلميح 1
min(graph[city], key=lambda p: p[1]) يختار الزوج ذا أقل مسافة.💡 تلميح 2
sorted(graph) يرتب أسماء المدن.حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
roads = [("المدينة", "ينبع", 230), ("المدينة", "بدر", 150), ("ينبع", "رابغ", 180), ("بدر", "رابغ", 120), ("رابغ", "جدة", 150), ("جدة", "مكة", 80), ("مكة", "الطائف", 90), ("بدر", "مكة", 330)] graph = {}for a, b, km in roads: graph.setdefault(a, []).append((b, km)) graph.setdefault(b, []).append((a, km)) for city in sorted(graph): near, km = min(graph[city], key=lambda p: p[1]) print(f"{city} ← {near} ({km})")