الدرس 19 · الوحدة 8: اختيار خوارزمية للحل
البحث في الرسوم: BFS و DFS
كيف يجد تطبيق الخرائط طريقًا، وكيف تخرج من متاهة؟ ⏱ نحو 40 دقيقة.
بعد هذا الدرس ستستطيع أن:
- تشرح فكرة
BFSوDFSوالتركيب الذي يستخدمه كل منهما. - تنفذ
BFSبالطابور وDFSبالعودية وبالمكدس. - تجد أقصر مسار بعدد الأضلاع بـ
BFSوتتتبعه بقاموس الآباء. - تطبق البحث على المتاهات وتحسب تعقيده
O(V + E).
١طريقتان لزيارة كل العقد
| البحث بالعرض BFS | البحث بالعمق DFS | |
|---|---|---|
| الفكرة | زُر كل الجيران أولًا، ثم جيران الجيران: طبقة بعد طبقة. | اذهب في طريق إلى أبعد ما يمكن، ثم ارجع وجرّب طريقًا آخر. |
| التركيب | طابور deque | مكدس (أو العودية) |
| تشبيه | موجة تنتشر من حجر في الماء | مستكشف في متاهة يتبع جدارًا |
| أهم استخدام | أقصر مسار بعدد الأضلاع | اكتشاف الحلقات، وكل المسارات، والمتاهات |
٢البحث بالعرض BFS
graph = { "المدينة": ["ينبع", "بدر"], "ينبع": ["المدينة", "رابغ"], "بدر": ["المدينة", "رابغ", "مكة"], "رابغ": ["ينبع", "بدر", "جدة"], "جدة": ["رابغ", "مكة"], "مكة": ["جدة", "الطائف", "بدر"], "الطائف": ["مكة"],} from collections import deque def bfs(start): visited = {start} order = [] queue = deque([start]) while queue: city = queue.popleft() order.append(city) for nb in graph[city]: if nb not in visited: # set: فحص O(1) visited.add(nb) queue.append(nb) return order print(" ← ".join(bfs("المدينة")))
>>> %Run main.py
المدينة ← ينبع ← بدر ← رابغ ← مكة ← جدة ← الطائف
>>>
لاحظ: ينبع وبدر (المسافة 1) قبل رابغ ومكة (المسافة 2) قبل جدة والطائف (المسافة 3). التعقيد O(V + E): كل عقدة تدخل الطابور مرة، وكل ضلع يُفحص مرة من كل جهة.
٣أقصر مسار بعدد المحطات
لأن BFS يزور العقد بترتيب بعدها، فأول مرة نصل إلى عقدة تكون عبر أقصر مسار بعدد الأضلاع. نحفظ من أين جئنا لكل عقدة، ثم نتتبع الطريق عكسيًّا:
graph = { "المدينة": ["ينبع", "بدر"], "ينبع": ["المدينة", "رابغ"], "بدر": ["المدينة", "رابغ", "مكة"], "رابغ": ["ينبع", "بدر", "جدة"], "جدة": ["رابغ", "مكة"], "مكة": ["جدة", "الطائف", "بدر"], "الطائف": ["مكة"],} from collections import deque def shortest_path(start, goal): parent = {start: None} queue = deque([start]) while queue: city = queue.popleft() if city == goal: break for nb in graph[city]: if nb not in parent: parent[nb] = city queue.append(nb) path, cur = [], goal while cur is not None: path.append(cur) cur = parent[cur] return path[::-1] print(" ← ".join(shortest_path("المدينة", "الطائف")))print(" ← ".join(shortest_path("ينبع", "مكة")))
>>> %Run main.py
المدينة ← بدر ← مكة ← الطائف
ينبع ← المدينة ← بدر ← مكة
>>>
هذا أقصر بعدد المدن، لا بالكيلومترات. للمسافات الموزونة نحتاج خوارزمية دايكسترا (الدرس 24).
٤البحث بالعمق DFS
graph = { "المدينة": ["ينبع", "بدر"], "ينبع": ["المدينة", "رابغ"], "بدر": ["المدينة", "رابغ", "مكة"], "رابغ": ["ينبع", "بدر", "جدة"], "جدة": ["رابغ", "مكة"], "مكة": ["جدة", "الطائف", "بدر"], "الطائف": ["مكة"],} def dfs(city, visited, order): visited.add(city) order.append(city) for nb in graph[city]: if nb not in visited: dfs(nb, visited, order) # تعمّق قبل الانتقال للجار التالي return order print(" ← ".join(dfs("المدينة", set(), [])))
>>> %Run main.py
المدينة ← ينبع ← رابغ ← بدر ← مكة ← جدة ← الطائف
>>>
graph = { "المدينة": ["ينبع", "بدر"], "ينبع": ["المدينة", "رابغ"], "بدر": ["المدينة", "رابغ", "مكة"], "رابغ": ["ينبع", "بدر", "جدة"], "جدة": ["رابغ", "مكة"], "مكة": ["جدة", "الطائف", "بدر"], "الطائف": ["مكة"],} def dfs_stack(start): visited, order = set(), [] stack = [start] while stack: city = stack.pop() if city in visited: continue visited.add(city) order.append(city) for nb in reversed(graph[city]): if nb not in visited: stack.append(nb) return order print(" ← ".join(dfs_stack("المدينة")))
>>> %Run main.py
المدينة ← ينبع ← رابغ ← بدر ← مكة ← جدة ← الطائف
>>>
النسختان تعطيان الترتيب نفسه: العودية تستخدم مكدس الاستدعاءات، والثانية مكدسًا صريحًا. ونستخدم reversed لنزور الجيران بترتيبهم في القائمة.
٥تطبيق: الخروج من متاهة
المتاهة رسم بياني مخفي: كل خانة مفتوحة عقدة، وجيرانها الخانات المفتوحة فوقها وتحتها ويمينها ويسارها. BFS يجد أقصر طريق:
from collections import deque maze = ["S.#.....", ".##.###.", "....#...", ".##...#E"] rows, cols = len(maze), len(maze[0])start, end = (0, 0), (3, 7)dist = {start: 0}queue = deque([start])while queue: r, c = queue.popleft() for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in dist: dist[(nr, nc)] = dist[(r, c)] + 1 queue.append((nr, nc)) print("أقل عدد خطوات:", dist.get(end, "لا طريق"))
>>> %Run main.py
أقل عدد خطوات: 12
>>>
توقّع وتحقّق
BFS يستخدم:
طبقة بعد طبقة.
DFS العودي يستخدم ضمنيًّا:
العودية.
أقصر مسار بعدد الأضلاع في رسم غير موزون:
يزور بترتيب البعد.
تعقيد BFS و DFS بقائمة الجوار:
كل عقدة وضلع مرة.
الخلاصة
BFS: طابور، طبقة بعد طبقة، ويجد أقصر مسار بعدد الأضلاع.DFS: مكدس أو عودية، يتعمق ثم يرجع.visitedضروري لتجنب الحلقات، وsetتجعل فحصهO(1).- التعقيد
O(V + E)، والمتاهة رسم مخفي.
تحدٍّ برمجي: كم مدينة على بعد محطتين؟
متوسطعدّل BFS ليحسب المسافة (بعدد الطرق) من المدينة إلى كل مدينة، ثم اطبع المدن على كل مسافة.
المطلوب:
- قاموس dist: المدينة ← عدد الطرق من البداية.
- اطبع لكل مسافة من 0 إلى أكبرها المدن مرتبة أبجديًّا، فيكون السطر الثاني:
1: ['بدر', 'ينبع']
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
graph = { "المدينة": ["ينبع", "بدر"], "ينبع": ["المدينة", "رابغ"], "بدر": ["المدينة", "رابغ", "مكة"], "رابغ": ["ينبع", "بدر", "جدة"], "جدة": ["رابغ", "مكة"], "مكة": ["جدة", "الطائف", "بدر"], "الطائف": ["مكة"],} from collections import deque dist = {"المدينة": 0}
0: ['المدينة']
1: ['بدر', 'ينبع']
2: ['رابغ', 'مكة']
3: ['الطائف', 'جدة']
💡 تلميح 1
dist[nb] = dist[city] + 1 عند أول وصول.💡 تلميح 2
sorted(c for c in dist if dist[c] == d)حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
graph = { "المدينة": ["ينبع", "بدر"], "ينبع": ["المدينة", "رابغ"], "بدر": ["المدينة", "رابغ", "مكة"], "رابغ": ["ينبع", "بدر", "جدة"], "جدة": ["رابغ", "مكة"], "مكة": ["جدة", "الطائف", "بدر"], "الطائف": ["مكة"],} from collections import deque dist = {"المدينة": 0}queue = deque(["المدينة"])while queue: city = queue.popleft() for nb in graph[city]: if nb not in dist: dist[nb] = dist[city] + 1 queue.append(nb) for d in range(max(dist.values()) + 1): print(f"{d}:", sorted(c for c in dist if dist[c] == d))