📄 النص الكامل للصفحة
--- SECTION: 4 --- في المخطط على اليسار، انتقل من عقدة البداية A إلى عقدة الهدف G. طبق خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام هيكل البيانات المناسب (المكدس أو الطابور)، مع الإشارة إلى العقد التي فحصت.2023 - 1447--- VISUAL CONTEXT ---
**DIAGRAM**: Untitled Description: A tree diagram illustrating a graph structure with nodes labeled A through M. Node A is the root, connected to B, C, D. Node B is connected to E, F. Node C is connected to G. Node D is connected to H, I, J. Node E is connected to K. Node G is connected to L, M. The diagram shows a hierarchical relationship between the nodes.
Data: The diagram represents a graph where nodes are connected. The task involves traversing this graph from a start node (A) to a target node (G).
Key Values: Nodes: A, B, C, D, E, F, G, H, I, J, K, L, M, Start Node: A, Target Node: G Context: This diagram is the visual representation of the problem described in question 4, which requires applying Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms to find a path from node A to node G.**TABLE**: Untitled Description: A large, empty grid with numerous rows and columns, likely intended as a workspace for students to record the steps and nodes examined during the application of the BFS and DFS algorithms as per question 4.
Table Structure:
Headers: N/A Rows:
Empty cells: All cells are empty, awaiting student input for algorithm tracing.
Calculation needed: To record the sequence of visited nodes and the state of the data structure (stack/queue) for BFS and DFS algorithms.
Data: The grid is empty, indicating it is a blank space for user input or calculations.
Context: Provides a structured area for students to document their work for the algorithm tracing exercise.
📝 أسئلة اختبارية
عدد الأسئلة: 3
سؤال 4: في المخطط على اليسار، انتقل من عقدة البداية A إلى عقدة الهدف G. طبق خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام هيكل البيانات المناسب (المكدس أو الطابور)، مع الإشارة إلى العقد التي فحصت.
الإجابة الصحيحة: انظر الأسئلة الفرعية
الشرح: هذا سؤال رئيسي يحتوي على أسئلة فرعية تتطلب تطبيق خوارزميتي BFS و DFS
تلميح: استخدم المخطط المرفق لتتبع مسار الخوارزميات
سؤال 4: طبق خوارزمية البحث بأولوية الاتساع (BFS) للانتقال من عقدة البداية A إلى عقدة الهدف G
- أ) مسار: A → B → C → G، العقد: A, B, C, G، هيكل: طابور
- ب) مسار: A → C → G، العقد: A, C, G، هيكل: طابور
- ج) مسار: A → B → C → D → E → F → G، العقد: A, B, C, D, E, F, G، هيكل: طابور
- د) مسار: A → D → H → I → J → C → G، العقد: A, D, H, I, J, C, G، هيكل: طابور
الإجابة الصحيحة: مسار BFS: A → B → C → D → E → F → G (عند الوصول إلى G من C). العقد المفحوصة: A, B, C, D, E, F, G. هيكل البيانات: طابور (Queue)
الشرح: خوارزمية BFS تفحص العقد مستوىً بمستوى. من A تفحص B, C, D (المستوى الأول)، ثم من B تفحص E, F (المستوى الثاني)، ومن C تصل إلى G (الهدف).
تلميح: تذكر أن BFS تستخدم الطابور وتفحص الجيران الأقرب أولاً
سؤال 4: طبق خوارزمية البحث بأولوية العمق (DFS) للانتقال من عقدة البداية A إلى عقدة الهدف G
- أ) مسار: A → C → G، العقد: A, C, G، هيكل: مكدس
- ب) مسار: A → B → E → K → F → C → G، العقد: A, B, E, K, F, C, G، هيكل: مكدس
- ج) مسار: A → D → H → I → J → C → G، العقد: A, D, H, I, J, C, G، هيكل: مكدس
- د) مسار: A → B → C → G، العقد: A, B, C, G، هيكل: مكدس
الإجابة الصحيحة: مسار DFS: A → B → E → K → F → C → G (عند الوصول إلى G من C). العقد المفحوصة: A, B, E, K, F, C, G. هيكل البيانات: مكدس (Stack)
الشرح: خوارزمية DFS تفحص الفرع بأكمله قبل الانتقال إلى الفرع التالي. من A تذهب إلى B ثم إلى E ثم إلى K ثم تعود إلى F ثم إلى C ثم تصل إلى G.
تلميح: تذكر أن DFS تستخدم المكدس وتذهب إلى أعمق نقطة ممكنة أولاً
🎴 بطاقات تعليمية للمراجعة
عدد البطاقات: 5 بطاقة لهذه الصفحة
طبق خوارزمية البحث بأولوية الاتساع (BFS) على المخطط المعطى، بدءاً من العقدة A وصولاً إلى العقدة G. اذكر العقد التي تم فحصها بالترتيب، مع الإشارة إلى هيكل البيانات المستخدم (الطابور).
الإجابة: يبدأ البحث من العقدة A.
1. فحص A. يضاف أبناء A (B, C, D) إلى الطابور. الطابور: [B, C, D].
2. فحص B. يضاف أبناء B (E, F) إلى الطابور. الطابور: [C, D, E, F].
3. فحص C. يضاف أبناء C (G) إلى الطابور. الطابور: [D, E, F, G].
4. فحص D. يضاف أبناء D (H, I, J) إلى الطابور. الطابور: [E, F, G, H, I, J].
5. فحص E. يضاف أبناء E (K) إلى الطابور. الطابور: [F, G, H, I, J, K].
6. فحص F. ليس لها أبناء. الطابور: [G, H, I, J, K].
7. فحص G. تم الوصول إلى الهدف.
العقد المفحوصة بالترتيب: A, B, C, D, E, F, G.
الشرح: خوارزمية BFS تفحص العقد مستوى بمستوى. تبدأ بالعقدة الجذر ثم تفحص جميع جيرانها، ثم جيران الجيران، وهكذا. الطابور (Queue) هو هيكل البيانات المناسب لتنفيذ BFS لأنه يحافظ على ترتيب الوصول (FIFO - First-In, First-Out).
تلميح: تذكر أن خوارزمية BFS تعتمد على هيكل بيانات يضيف العناصر في الأمام ويخرجها من الخلف. ما هو اسم هذا الهيكل؟
طبق خوارزمية البحث بأولوية العمق (DFS) على المخطط المعطى، بدءاً من العقدة A وصولاً إلى العقدة G. اذكر العقد التي تم فحصها بالترتيب، مع الإشارة إلى هيكل البيانات المستخدم (المكدس).
الإجابة: يبدأ البحث من العقدة A.
1. فحص A. يضاف أبناء A (D, C, B) إلى المكدس (يفضل البدء بأبناء بترتيب عكسي لسهولة التتبع أو حسب الترتيب المعطى في الرسم). لنفترض إضافة B, C, D. المكدس: [B, C, D].
2. فحص B. يضاف أبناء B (F, E). المكدس: [F, E, C, D].
3. فحص F. ليس لها أبناء. المكدس: [E, C, D].
4. فحص E. يضاف أبناء E (K). المكدس: [K, C, D].
5. فحص K. ليس لها أبناء. المكدس: [C, D].
6. فحص C. يضاف أبناء C (G). المكدس: [G, D].
7. فحص G. تم الوصول إلى الهدف.
العقد المفحوصة بالترتيب: A, B, F, E, K, C, G. (قد يختلف الترتيب قليلاً بناءً على ترتيب إضافة الأبناء إلى المكدس، ولكن المسار سيبقى بنفس المنطق).
الشرح: خوارزمية DFS تتعمق في مسار واحد قدر الإمكان قبل التراجع. المكدس (Stack) هو هيكل البيانات المثالي لتنفيذ DFS لأنه يسمح بإضافة (Push) وإزالة (Pop) العناصر من نفس الطرف، مما يضمن استكشاف أعمق مسار أولاً.
تلميح: ما هو هيكل البيانات الذي يعمل بنظام "آخر من يدخل، أول من يخرج" (LIFO)؟ هذا هو الهيكل المناسب لـ DFS.
ما هو الفرق الأساسي في استراتيجية البحث بين خوارزميتي BFS و DFS عند استكشاف المخطط؟
الإجابة: خوارزمية BFS تستكشف المخطط بشكل عرضي (طبقة بطبقة)، حيث تفحص جميع العقد على عمق معين قبل الانتقال إلى المستوى التالي. بينما خوارزمية DFS تستكشف بشكل عميق، حيث تتعمق في مسار واحد قدر الإمكان قبل التراجع واستكشاف مسار آخر.
الشرح: طبيعة البحث العرضي (BFS) تجعلها تجد أقصر مسار في حالة الأوزان المتساوية. بينما طبيعة البحث العميق (DFS) قد تؤدي إلى إيجاد مسارات أطول ولكنها قد تكون أسرع في الوصول إلى حل في بعض الحالات.
تلميح: فكر في الطريقة التي تتسع بها كل خوارزمية في استكشافها للمخطط: هل تتجه نحو الخارج بشكل دائري أم نحو الأسفل في مسار واحد؟
ما هو هيكل البيانات الذي تُستخدمه خوارزمية BFS عادةً لتتبع العقد التي يجب زيارتها؟
الإجابة: تستخدم خوارزمية BFS عادةً هيكل بيانات الطابور (Queue).
الشرح: الطابور يضمن أن العقد التي تم اكتشافها أولاً (أي على مستويات أقرب للجذر) يتم فحصها أولاً، مما يحقق خاصية البحث العرضي.
تلميح: ما هو المبدأ الذي يعمل به هذا الهيكل؟ "الأول يدخل، الأول يخرج"؟
ما هو هيكل البيانات الذي تُستخدمه خوارزمية DFS عادةً لتتبع العقد التي يجب زيارتها؟
الإجابة: تستخدم خوارزمية DFS عادةً هيكل بيانات المكدس (Stack).
الشرح: المكدس يسمح بالوصول إلى أحدث عقدة تم إضافتها، مما يمكن الخوارزمية من التعمق في مسار جديد عند زيارة عقدة، والتراجع إلى آخر عقدة تم زيارتها إذا وصل المسار إلى طريق مسدود.
تلميح: ما هو المبدأ الذي يعمل به هذا الهيكل؟ "الأخير يدخل، الأول يخرج"؟