الرسوم البيانية
الرسوم البيانية
- الرسم البياني هو مجموعة من العقد (تسمى أيضاً الرؤوس) متصلة بواسطة حواف (روابط).
- تحاكي الرسوم البيانية الشبكات: الأصدقاء، الطرق بين المدن، الروابط بين صفحات الويب.
- الشجرة هي حقاً رسم بياني خاص؛ الرسم البياني العام يمكن أن يحتوي على حلقات وعديد من الروابط لكل عقدة.
تمثيل الرسم البياني: القائمة المجاورة
- إحدى الطرق الشائعة هي القائمة المجاورة: قاموس يربط كل عقدة بـقائمة جيرانها.
graph["A"]هي قائمة العقد المتصلة مباشرة بـA.- هذا تمثيل مدمج عندما يكون لكل عقدة عدد قليل من الاتصالات فقط.
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
إضافة حافة
- في الرسم البياني غير الموجه، الحافة
A—Bتسير في الاتجاهين. - لذا فإن إضافتها تعني إضافة
Bإلى قائمةAوAإلى قائمةB. - إذا كانت العقدة جديدة، ابدأ بقائمة فارغة أولاً.
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
التجول عبر الجيران
- لاستكشاف نقطة ما، تقرأ قائمة جيرانها تزور واحداً تلو الآخر.
- العقدة التي لا توجد في الرسم البياني ليس لها جيران — أعد قائمة فارغة، وليس خطأ.
- هذا الاستعلام عن الجيران هو الخطوة الأولى لمهام أكبر مثل البحث في الرسم البياني بالكامل.
موجه مقابل غير موجه
- في رسم بياني غير موجه تعمل الحافة في كلا الاتجاهين (صداقة).
- في رسم بياني موجه تشير الحافة في اتجاه واحد فقط (شارع ذو اتجاه واحد، رابط "يتبع").
- بالنسبة للحواف الموجهة، ستضيف في اتجاه واحد فقط.
أخطاء شائعة
- الرسم البياني هو عقد متصلة بحواف؛ يمكن أن تكون الحافة ذات اتجاه واحد أو اتجاهين.
- الشجرة هي رسم بياني بدون حلقات — لا تخلط بينهما.
الآن جرب بنفسك
- بنِ عمليات القائمة المجاورة:
add_edge،neighbours، وcount_edges. - كل مهمة تتحقق من دالة على رسم بياني صغير.
- اضغط على تحقق من الإجابة لاختبارها.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب add_edge(graph, a, b) لرسم بياني غير موجه مخزن كقاموس لقوائم الجيران. أضف b إلى graph[a] وأضف a إلى graph[b]. إذا كان العُقد غير موجود في الرسم البياني حتى الآن، أعطه قائمة فارغة [] أولاً. عدل القاموس محلياً.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب neighbours(graph, node) الذي يُرجع قائمة العقد المتصلة مباشرة بـ node. إذا لم يكن node في الرسم البياني، أرجع قائمة فارغة [] (لا ترفع خطأ).
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب count_edges(graph) لرسم بياني غير موجه: عدّ كم عدد الحواف له. اجمع أطوال كل قائمة مجاورات، ثم اقسم على 2 (كل حافة مخزنة في قوائم كلا العقدتين). مثال: مثلث A–B–C لديه 3 حواف.
اضغط تشغيل لرؤية المخرجات هنا.