انتقل إلى المحتوى
أمين أبوزيد
Englishالعربية
BEG-043

أساسيات الرسوم البيانية (Graphs)

  • 6 درس
  • 71 دقيقة قراءة
  • 3 ساعة تدريب (تقدير)
ابدأ الوحدة
في هذه الصفحة 8 موضوعات

نص الدروس والتمارين باللغة الإنجليزية، بينما تبقى واجهة الموقع وعناوين الدروس بالعربية.

نظرة عامة

الموضوعات

  • الرؤوس (Vertices)
  • الحواف (edges)
  • BFS
  • DFS
  • التطبيقات الشائعة

تعلّم أولًا

71 دقيقة قراءة · 3 ساعة تدريب (تقدير)

مخرجات التعلم

  1. Represent a graph with an adjacency list.
  2. Implement BFS and DFS and choose between them.
  3. Find a shortest path in an unweighted graph with BFS.
  4. Recognize graph problems in real systems (dependencies, networks, routes).

الدروس

  1. 01الرسوم البيانية (Graphs) في كل مكان12 د قراءة
  2. 02تمثيل الرسوم البيانية12 د قراءة
  3. 03البحث بالعرض أولاً (Breadth-first search)12 د قراءة
  4. 04البحث بالعمق أولاً (Depth-first search)12 د قراءة
  5. 05التطبيقات: الاعتماديات والدورات11 د قراءة
  6. 06عرض عملي: إيجاد مسار المترو باستخدام BFS12 د قراءة

المختبر والتمارين

Lab

BEG-043-LAB1 · Metro route finder

Outcomes: 1–4 · Time: ~3 h

  1. Load a small metro map (a text file of "station-station" lines) into an adjacency list.
  2. Implement BFS that returns the fewest-stops route between two stations.
  3. Handle unknown and unreachable stations without crashing.
  4. Add a DFS "can I get there at all" check and say when you would use it instead of BFS.

Acceptance: correct routes; unreachable stations handled.

Exercises (assessment: 3 problems)

IDOutcomeTask
BEG-043-EX011Write the adjacency list for edges A-B, A-C, B-D, C-D, D-E (undirected).
BEG-043-EX022Write the BFS visiting order from A for the graph in EX01 (visit neighbors in alphabetical order).
BEG-043-EX032Write the DFS visiting order from A for the same graph, same neighbor order.
BEG-043-EX043Using BFS, give the shortest path from A to E and its number of edges.
BEG-043-EX054Name the nodes and edges of: a course prerequisite plan; a social network; a map of airports and flights. Say whether each is directed.
BEG-043-EX062Explain what happens if BFS has no visited set on a graph with a cycle.
أظهر الحلول
  • EX01 A: [B, C]; B: [A, D]; C: [A, D]; D: [B, C, E]; E: [D].
  • EX02 A, B, C, D, E.
  • EX03 A, B, D, C, E (A -> B -> D -> C, back to D -> E).
  • EX04 A -> B -> D -> E (or via C), 3 edges.
  • EX05 Prerequisites: courses are nodes, "needs" are directed edges. Social network: people are nodes; "friend" is undirected, "follows" is directed. Airports: nodes airports, edges flights, usually directed.
  • EX06 It keeps re-adding the same nodes around the cycle and never finishes (an infinite loop or a memory error).

الاختبار

Outcomes: O1 adjacency list · O2 BFS and DFS · O3 shortest path · O4 graph problems in systems.

اختبار ذاتي لك: لا توجد درجات، ولا يُحفظ أو يُرسل أي شيء. اختر إجابة ثم تحقق منها، ويمكنك المحاولة مرة أخرى كما تشاء.

  1. 1A graph is made of:O1
  2. 2An adjacency list stores for each node:O1
  3. 3A one-way street is best modeled as a(n):O1
  4. 4BFS uses a:O2
  5. 5Without a visited set, BFS on a graph with a cycle may:O2
  6. 6Recursive DFS relies on the:O2
  7. 7In an unweighted graph, the shortest path (fewest edges) is found by:O3
  8. 8BFS time for V nodes and E edges with an adjacency list:O3
  9. 9"Library A needs B, B needs A" is a:O4
  10. 10Which is a graph problem?O4

الجزء العملي

Three problems (BEG-043-EX02, EX03, EX04) plus the metro route finder lab and exercises EX01, EX05, EX06. Pass: at least 2 of 3 problems correct, correct routes, unreachable stations handled, and at least 8 of 10 quiz answers correct.

أخطاء شائعة

Forgetting a visited set (infinite loops).

التقييم

3 problems.

الصلة بالمسار الوظيفي

Dependency mapping (SRC-009) and service graphs.

اكتب للبحث في المستويات والمراحل والوحدات والدروس.