الرسم البياني الموجه هو رسم بياني يتكون من رؤوس وأقواس ، حيث يكون لكل قوس اتجاه. أحد المجالات الرئيسية التي تستخدم فيها الرسوم البيانية الموجهة على نطاق واسع هو تحليل الشبكة ونمذجة عمليات نقل البيانات وحل مشكلات تحديد المسار واجتياز الرسم البياني.
في هذه المقالة ، سوف ننظر في كيفية إنشاء رسم بياني موجه في بيثون باستخدام مكتبة نيتورككس. نيتورككس هي مكتبة قوية توفر أدوات مريحة للعمل مع الرسوم البيانية ، بما في ذلك إنشاء وتعديل وتحليل وتصور الرسوم البيانية.
خطوة بخطوة ، سوف نتعلم كيفية إنشاء الرسوم البيانية الموجهة في بايثون ، وإضافة الرؤوس والأقواس إليها ، وتعيين سمات الرؤوس والأقواس ، وتحليل الرسوم البيانية الناتجة وتصورها. وسوف ننظر أيضا في مختلف الأساليب والخوارزميات المتاحة في مكتبة نيتورككس للعمل مع الرسوم البيانية الموجهة.
- المفاهيم والتعاريف الأساسية
- بناء رسم بياني موجه في بايثون
- استخدام مكتبة نيتورككس
- خوارزميات لمعالجة الرسوم البيانية الموجهة
- الفرز الطوبولوجي
- سؤال وجواب
- كيف يمكنني إنشاء رسم بياني موجه في بيثون?
- كيفية تصور رسم بياني موجه في بيثون?
- كيف يمكنني إضافة رؤوس وحواف جديدة إلى رسم بياني موجه تم إنشاؤه بالفعل?
- هل من الممكن لبناء الرسم البياني باستخدام مصفوفة الجوار?
المفاهيم والتعاريف الأساسية
الرسم البياني الموجه هو تجريد رياضي يمثل مجموعة من العقد المتصلة ببعضها البعض بواسطة حواف موجهة.
تمثل كل عقدة في الرسم البياني الموجه كائنا أو كيانا ، وتمثل الحافة علاقة أو اتصالا بين عقدتين. الحواف في الرسم البياني الموجه لها اتجاه يشير إلى العقدة التي نشأت منها والعقدة التي تدخلها.
يمكن اعتبار الرسم البياني الموجه كمجموعة من العقد والحواف ، حيث يمكن توصيل العقد باستخدام حافة واحدة أو أكثر. يمكن أن يكون لكل حافة في الرسم البياني الموجه وزن معين ، والذي يمكن استخدامه لتقييم درجة الترابط بين العقد.
يمكن استخدام الرسم البياني الموجه لنمذجة أنظمة وشبكات مختلفة ، مثل الشبكات الاجتماعية وشبكات النقل والدوائر الكهربائية والمزيد. يمكن استخدامه أيضا لحل المهام المختلفة ، على سبيل المثال ، العثور على أقصر مسار بين عقدتين أو تحديد أهم العقد في الرسم البياني.
يمكن تمثيل الرسم البياني الموجه كجدول مجاور أو قوائم مجاورة. في الجدول المجاور ، يتوافق كل صف وعمود مع عقد الرسم البياني ، وتشير عناصر الجدول إلى وجود أو عدم وجود حافة بين العقد. في قوائم الجوار ، يتم تمثيل كل عقدة كعنصر قائمة ، ويتم تمثيل الحواف كعقد متصلة داخل القائمة.
بناء رسم بياني موجه في بايثون
الرسم البياني الموجه هو رسم بياني يكون فيه لكل حافة اتجاه. بيثون لديها العديد من المكتبات التي تسمح لك لبناء والعمل مع الرسوم البيانية الموجهة ، مثل نيتورككس و إيغراف.
لبدء العمل مع رسم بياني موجه في بيثون ، تحتاج إلى استيراد المكتبة اللازمة وإنشاء رسم بياني فارغ:
استيراد نيتورككس كما نكسز = نكس.ديغراف()
بعد ذلك ، يمكنك إضافة رؤوس وحواف إلى الرسم البياني:
ز. إضافة العقد (1)ز. إضافة العقد(2)
زاي-إضافة العقد (3)
زاي-الحافة الإضافية (1 ، 2)
زاي-الحافة الإضافية(2، 3)
زاي-الحافة الإضافية (3 ، 1)
في هذا المثال ، أنشأنا رسما بيانيا بثلاثة رؤوس وأضفنا ثلاثة حواف تشكل دورة. هذا يعني أنه من الرأس 1 يمكنك الوصول إلى الرأس 2 ، ومن الرأس 2 إلى الرأس 3 ، ومن الرأس 3 إلى الرأس 1.
يمكنك الحصول على قائمة بجميع رؤوس وحواف الرسم البياني على النحو التالي:
طباعة (ز. العقد)طباعة (ز الحواف)
يمكنك أيضا الحصول على قائمة من القمم المجاورة لكل قمة من الرسم البياني:
للعقدة في العقد:الجيران = جي الجيران (العقدة)
طباعة (و " القمم المجاورة للرأس {عقدة}: {قائمة (الجيران)}")
لتصور رسم بياني موجه ، يمكنك استخدام وظيفة الرسم من مكتبة نيتورككس:
استيراد ماتلوتليب.بيبلوت كما بلتنكس.رسم (ز ، مع_التسميات = صحيح)
قانون العمل.عرض()
نتيجة لتنفيذ هذا الرمز ، سيتم عرض صورة الرسم البياني باستخدام مكتبة ماتلوتليب.
من الممكن أيضا تطبيق خوارزميات وعمليات مختلفة على الرسوم البيانية الموجهة ، مثل البحث عن أقصر مسار ، والبحث عن الدورة ، وما إلى ذلك. لمزيد من المعلومات حول العمل مع الرسوم البيانية الموجهة في بيثون ، راجع وثائق مكتبة نيتورككس.
استخدام مكتبة نيتورككس
مكتبة نيتورككس هو أداة قوية للعمل مع الرسوم البيانية الموجهة في لغة البرمجة بيثون. يوفر مجموعة واسعة من الوظائف لإنشاء الرسوم البيانية وتصورها وتحليلها.
الخطوة 1: تثبيت مكتبة نيتورككس
قبل البدء في العمل مع مكتبة نيتورككس ، تحتاج إلى تثبيته. للقيام بذلك ، يمكنك استخدام مدير حزمة النقطة عن طريق تشغيل الأمر التالي:
بيب تثبيت نيتورككسالخطوة 2: إنشاء رسم بياني موجه
بعد تثبيت مكتبة نيتورككس ، يمكنك البدء في إنشاء رسم بياني موجه. للقيام بذلك ، تحتاج إلى استيراد الوحدة النمطية المناسبة:
استيراد نيتورككس كما نكسثم قم بإنشاء رسم بياني موجه فارغ:
ز = نكس.ديغراف()الخطوة 3: إضافة القمم والحواف
على التوالي:
زاي-إضافة العقد ('أ')زاي-إضافة العقد ('ب')
زاي-الحافة الإضافية ('أ' ، 'ب')
في هذا المثال ، يتم إضافة القمم 'أ' و 'ب' ، وكذلك حافة موجهة من قمة الرأس ' أ 'إلى قمة الرأس 'ب'.
الخطوة 4: تصور الرسم البياني
:
نكس.رسم (ز ، مع_التسميات = صحيح)يضمن أن يتم عرض تسميات قمة الرأس على الرسم البياني.
الخطوة 5: تحليل الرسم البياني
توفر مكتبة نيتورككس أيضا وظائف لتحليل الرسم البياني الموجه. يمكن استخدامها لتحديد عدد الرؤوس والحواف ، والعثور على المسارات بين الرؤوس ، وتنفيذ عمليات حسابية أخرى.
وفقا لذلك:
عدد العقد = عدد العقد ()عدد الحواف = عدد الحواف ()
وهكذا ، فإن مكتبة نيتورككس يسمح لك لخلق الرسوم البيانية الموجهة ، تصور وتحليلها ، مما يجعلها أداة ممتازة للعمل مع الرسوم البيانية في بيثون.
خوارزميات لمعالجة الرسوم البيانية الموجهة
الرسم البياني الموجه هو بنية بيانات مهمة تعتمد عليها العديد من الخوارزميات والتطبيقات. تتضمن معالجة الرسم البياني الموجه حل مهام مختلفة مثل البحث عن أقصر مسار ، والفرز الطوبولوجي ، والبحث عن الدورة ، والعثور على مكونات الاتصال ، وغيرها الكثير.
هناك العديد من الخوارزميات لمعالجة الرسوم البيانية الموجهة ، كل منها يحل مشكلة معينة. فيما يلي بعض الخوارزميات الأكثر شيوعا:
- خوارزمية ديكسترا: تستخدم للعثور على أقصر مسار من قمة واحدة إلى أخرى. وهو يعمل على أساس مبدأ الاختيار الجشع ، واختيار قمة الرأس مع أصغر مسافة في كل خطوة.
- خوارزمية بيلمان فورد: تستخدم أيضا للعثور على أقصر مسار ، ولكن يمكنها العمل مع الرسوم البيانية ذات أوزان الحواف السالبة. يكرر استرخاء حواف الرسم البياني طالما أنه من الممكن تحسين المسافة الحالية.
- خوارزمية فلويد وارشال: تستخدم للعثور على أقصر المسارات بين جميع أزواج الرؤوس في الرسم البياني. ويستخدم البرمجة الديناميكية لبناء مصفوفة المسافة.
- خوارزمية تارجان: تستخدم للعثور على مكونات الاتصال القوي في رسم بياني موجه. يستخدم تقنية عبور الرسم البياني بعمق وحساب وقت الدخول والخروج من القمم.
- خوارزمية كوساراجو: تستخدم أيضا للعثور على مكونات الاتصال القوي ، ولكنها تعمل في الوقت الخطي. وهو يتألف من مرحلتين: إعادة توجيه الرسم البياني واجتياز الرسم البياني في العمق.
اعتمادا على المهمة المحددة ، قد يكون اختيار خوارزمية لمعالجة الرسم البياني الموجه مهمة محددة في حد ذاته. يمكن أن يؤدي تطبيق الخوارزمية الصحيحة إلى تسريع معالجة الرسم البياني بشكل كبير وإعطاء النتائج المرجوة.
تعد دراسة الخوارزميات لمعالجة الرسوم البيانية الموجهة خطوة مهمة في فهم كيفية عمل الخوارزميات والتطبيقات المختلفة. بمساعدتهم ، يمكنك حل العديد من المشكلات المتعلقة بالرسوم البيانية الموجهة وإنشاء حلول فعالة ومثالية.
الفرز الطوبولوجي
الفرز الطوبولوجي هو خوارزمية يتم تطبيقها على الرسوم البيانية الحلقية الموجهة (داغ) لترتيب القمم بطريقة لكل حافة (ش, الخامس) ، قمة الرأس ش يسبق قمة الرأس الخامس.
يمكن استخدام الفرز الطوبولوجي في العديد من المهام العملية ، على سبيل المثال ، في تصميم المجمعين لتحديد ترتيب حساب المشغلين أو في تخطيط المهام في الإنتاج.
يتم إجراء الفرز الطوبولوجي على النحو التالي:
- يتم تحديد أي قمة ليس لها حواف واردة (قمة بدون أسلاف).
- تتم إضافة الرأس المحدد إلى التسلسل النهائي.
- يتم حذف جميع الحواف القادمة من الرأس المحدد.
- تتكرر الخطوات من 1 إلى 3 للرؤوس المتبقية حتى تتم معالجة الرسم البياني بأكمله.
سيكون التسلسل النهائي للرؤوس هو الترتيب الطوبولوجي المطلوب. إذا كانت هناك دورات في الرسم البياني ، فلن يكون الفرز الطوبولوجي ممكنا.
في بيثون ، يمكنك استخدام وحدة 'نيتورككس' لأداء الفرز الطوبولوجي. للقيام بذلك ، قم بإنشاء رسم بياني موجه عن طريق تحديد اتجاه الحواف ، ثم قم باستدعاء الدالة `طوبولوجيكال_سورت`.
مثال رمز للفرز الطوبولوجي باستخدام وحدة ' نيتورككس` :
استيراد نيتورككس كما نكس
# إنشاء رسم بياني موجه فارغ
ز = نكس.ديغراف()
# إضافة القمم
['أ' ، 'ب' ، 'ج' ، 'د' ، 'ه' ، 'و'])
# إضافة حواف
من ج.([('أ' ، 'ب') ، ('ب' ، 'ج') ، ('ج' ، 'د') ، ('د' ، 'ه') ، ('ه' ، 'و')])
# الفرز الطوبولوجي
طبولوجي_أمر = قائمة(نكس.طوبولوجي(ز))
#
إخراج الطباعة (الطبولوجيا)
في هذا المثال ، يتم إنشاء رسم بياني برؤوس أ ، ب ، ج ، د ، هـ ، و ، ثم تتم إضافة الحواف. وظيفة` طوبولوجيكال_سورت ' بإرجاع قائمة من القمم في الترتيب الطوبولوجي. ونتيجة لتنفيذ التعليمات البرمجية تكون قائمة ['أ' ، 'ب' ، 'ج' ، 'د' ، 'ه' ، 'و'].
وبالتالي ، يتيح لك الفرز الطوبولوجي ترتيب الرؤوس في رسم بياني موجه ، مع مراعاة اتجاه الحواف. يمكن أن يكون مفيدا في المهام المختلفة التي تتطلب طلب الإجراءات أو الحسابات.
سؤال وجواب
كيف يمكنني إنشاء رسم بياني موجه في بيثون?
مكتبات مختلفة مثل نيتورككس يمكن استخدامها لإنشاء رسم بياني موجه في بيثون. الخطوة الأولى هي تثبيت المكتبة ، ثم البدء في إنشاء الرسم البياني. للقيام بذلك ، يمكنك استخدام وظيفة الإضافة لإضافة حواف موجهة بين رؤوس الرسم البياني. يمكنك أيضا استخدام وظيفة الإضافة لإضافة رؤوس جديدة. في النهاية ، يمكنك تصور الرسم البياني باستخدام وظيفة الرسم.
كيفية تصور رسم بياني موجه في بيثون?
لتصور رسم بياني موجه في بيثون ، يمكنك استخدام مكتبة نيتورككس. بعد إنشاء الرسم البياني باستخدام وظائف إضافة حافة وإضافة عقدة ، يمكنك استدعاء وظيفة الرسم لتصور الرسم البياني. تعرض هذه الوظيفة رؤوس الرسم البياني واتصالاتها. بالإضافة إلى ذلك ، يمكنك تعيين سمات مختلفة من القمم والحواف لتصور أكثر تفصيلا.
كيف يمكنني إضافة رؤوس وحواف جديدة إلى رسم بياني موجه تم إنشاؤه بالفعل?
لإضافة رأس جديد إلى رسم بياني موجه تم إنشاؤه بالفعل في بايثون،يمكنك استخدام وظيفة الإضافة. يجب عليك تحديد المعرف الفريد للرأس الجديد كوسيطة. لإضافة حافة جديدة بين الرؤوس الموجودة في الرسم البياني ، يمكنك استخدام وظيفة الإضافة. في هذه الحالة ، تحتاج إلى تحديد معرفات رؤوس البداية والنهاية ، بالإضافة إلى سمات الحافة الأخرى ، إن وجدت.
هل من الممكن لبناء الرسم البياني باستخدام مصفوفة الجوار?
نعم ، من الممكن إنشاء رسم بياني موجه باستخدام مصفوفة الجوار في بايثون. المصفوفة المجاورة هي مصفوفة ثنائية الأبعاد تقع فيها رؤوس الرسم البياني عموديا وأفقيا. تشير القيمة في خلية المصفوفة إلى وجود أو عدم وجود حافة بين الرؤوس. إذا كانت هناك حافة ، فستكون القيمة غير صفرية. لإنشاء رسم بياني بناء على مصفوفة الجوار ، يجب عليك أولا إنشاء رسم بياني فارغ ، ثم إضافة حواف وفقا للمصفوفة.