الرسوم البيانية هي واحدة من هياكل البيانات الرئيسية التي تستخدم على نطاق واسع في مختلف المجالات ، بدءا من علوم الكمبيوتر والبرمجة ، إلى الاقتصاد وعلم الاجتماع. في الرسم البياني ، العقد عبارة عن رؤوس ، والحواف عبارة عن روابط بين الرؤوس. يعد عدد المسارات بين رؤوس الرسم البياني مقياسا مهما يمكن أن يكون مفيدا في العديد من المهام. في هذه المقالة ، سنلقي نظرة على الطرق الرئيسية لحساب عدد المسارات في الرسم البياني ونقدم أمثلة على استخدامها.
تتمثل إحدى الطرق الرئيسية لحساب عدد المسارات في الرسم البياني في استخدام مصفوفات الجوار ومصفوفات الوقوع. المصفوفة المجاورة هي مصفوفة مربعة تتوافق فيها الصفوف والأعمدة مع رؤوس الرسم البياني ، وتشير قيم العناصر إلى وجود حافة بين الرؤوس المقابلة. مصفوفة الوقوع هي مصفوفة تتوافق فيها الصفوف مع الرؤوس والأعمدة تتوافق مع الحواف. يشار إلى وجود حافة بين قمة الرأس والحافة بالقيمة 1 ، ويشار إلى الغياب بالقيمة 0. يتم حساب عدد المسارات عن طريق رفع مصفوفة الجوار أو السقوط إلى قوة وإضافة العناصر المقابلة.
طريقة أخرى لحساب عدد المسارات في الرسم البياني هي استخدام خوارزمية اجتياز الرسم البياني في العمق أو العرض. عند عبور الرسم البياني بعمق ، يتم الانتقال من رأس واحد إلى رؤوس متجاورة بالتتابع حتى تتم زيارة جميع الرؤوس. أثناء الزحف ، يتم حساب عدد المسارات التي تم اجتيازها. يتم اجتياز الرسم البياني في العرض على مراحل ، في كل مرحلة تتم زيارة جميع القمم المجاورة ، ثم الانتقال إلى القمم المجاورة للمستوى التالي. يتم حساب عدد المسارات أيضا أثناء الزحف.
على سبيل المثال ، تخيل رسما بيانيا يوجد فيه ثلاثة رؤوس واتصالات بينهما: الرأس أ متصل بالرأس ب ، الرأس ب متصل بالرأس ج. لإيجاد عدد المسارات بين الرؤوس أ و ج ، يمكننا تربيع مصفوفة الجوار. نتيجة لذلك ، نحصل على القيم 0 ، 1 ، 0 لمصفوفة الجوار في الدرجة 2. وبالتالي ، فإن عدد المسارات بين القمم أ و ج هو 1.
- الطرق الأساسية لحساب عدد المسارات في الرسم البياني
- طريقة عدد من القمم والحواف
- طريقة مصفوفة الجوار
- أمثلة على حل مشكلة عد المسارات في الرسم البياني
- سؤال وجواب
- ما هي الطرق التي يمكن استخدامها لحساب عدد المسارات في الرسم البياني?
- كيف يمكنني استخدام طريقة العودية لحساب عدد المسارات في الرسم البياني?
- كيف تعمل طريقة جبر المصفوفة لحساب عدد المسارات في الرسم البياني?
الطرق الأساسية لحساب عدد المسارات في الرسم البياني
يمكن أن يكون حل المشكلات المتعلقة بحساب عدد المسارات في الرسم البياني مفيدا ، على سبيل المثال ، عند تحليل طرق النقل أو نمذجة الشبكات اللوجستية أو تحديد المسارات المحتملة في الأنظمة المعقدة.
هناك عدة طرق أساسية لحساب عدد المسارات في الرسم البياني:
- طريقة القوة الغاشمة
- طريقة المصفوفة
- الطريقة العودية
1. طريقة القوة الغاشمة
طريقة القوة الغاشمة هي الطريقة الأبسط والأكثر سهولة لحساب عدد المسارات في الرسم البياني. وهو يتألف من التكرار المتسلسل عبر جميع المسارات الممكنة وحساب عددها.
مثال:
عدد الدالة (الرسم البياني ، البداية ، النهاية) {
// Если стартовая и конечная вершины совпадают, то путь найден
إذا (بداية = = = نهاية) {
عودة 1;
}
// Иначе, рекурсивно перебираем все соседние вершины
دعونا العد = 0;
كونست الجيران = الرسم البياني [بداية];
ل (كونست جار الجيران) {
العد + = عدد المسارات (الرسم البياني ، الجار ، النهاية);
}
عد العودة;
}
كونست الرسم البياني = {
ج: ['ب' ، 'ج'],
ب: ['د'],
ج: ['د'],
د: ['ه'],
هاء: ['واو'],
و: []
};
وحدة التحكم.سجل (كونتباثس (الرسم البياني ، 'أ' ، 'و')) ؛ / / Вывод: 1
2. Матричный метод
تعتمد طريقة المصفوفة على تمثيل المصفوفة للرسم البياني وخوارزمية الأس لمصفوفة الجوار. في هذه الطريقة ، يتم حساب عدد المسارات في ا (سجل ن) ، أين ن هو عدد الرؤوس في الرسم البياني.
مثال:
عدد الدالة (مصفوفة ، بداية ، نهاية ، خطوات) {
كونست ن = مصفوفة.الطول;
// رفع مصفوفة الجوار إلى درجة الخطوات
دعونا بويردماتريكس = مصفوفة;
إلى عن على (دعني = 2; أنا < = خطوات ؛ أنا i) {
بويردماتريكس = مولتيبليماتريكس (بويردماتريكس ، مصفوفة);
}
عودة بويردماتريكس [بداية] [نهاية];
}
وظيفة مولتيبليماتريسس (ماتريكسا ، ماتريكسب) {
كونست ن = ماتريكسا.الطول;
كونست م = ماتريكسب [0].الطول;
نتيجة كونست = صفيف.من (صفيف (ن) ، () = > صفيف (م).ملء (0));
إلى عن على (دعني = 0 ؛ أنا < ن ؛ أنا {) {
إلى عن على (دع ي = 0 ؛ ي < م ؛ ي {) {
إلى عن على (دع ك = 0 ؛ ك < ماتريكسا[0].طول ؛ ك++) {
النتيجة [أنا] [ي] + = ماتريكسا [أنا] [ك] * ماتريكسب [ك] [ي];
}
}
}
نتيجة الإرجاع;
}
مصفوفة كونست = [
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]
];
وحدة التحكم.سجل (كونتباثس (مصفوفة, 0, 3, 2)); // :: 2
3. الطريقة العودية
تعتمد الطريقة العودية لحساب عدد المسارات في الرسم البياني على مبدأ البرمجة الديناميكية واستخدام ذاكرة التخزين المؤقت لتحسين العمليات الحسابية. تتيح لك هذه الطريقة تقليل عدد العمليات الحسابية المتكررة وزيادة سرعة البرنامج بشكل كبير.
مثال:
عدد الدالة (الرسم البياني ، البداية ، النهاية) {
كونست مخبأ = {};
وظيفة اجتياز (عقدة) {
// إذا تطابقت رؤوس البداية والنهاية ، فسيتم العثور على المسار
إذا (عقدة === نهاية) {
عودة 1;
}
// إذا تم حساب المسار مسبقا ، فأعده من ذاكرة التخزين المؤقت
إذا (مخبأ[عقدة]) {
عودة ذاكرة التخزين المؤقت [عقدة];
}
دعونا العد = 0;
// تكرار متكرر على جميع القمم المجاورة
كونست الجيران = الرسم البياني [عقدة];
ل (كونست جار الجيران) {
العد + = اجتياز (الجار);
}
// حفظ النتيجة في ذاكرة التخزين المؤقت
ذاكرة التخزين المؤقت [عقدة] = العد;
عد العودة;
}
عودة اجتياز (بداية);
}
كونست الرسم البياني = {
ج: ['ب' ، 'ج'],
ب: ['د'],
ج: ['د'],
د: ['ه'],
هاء: ['واو'],
و: []
};
وحدة التحكم.سجل (كونتباثس (الرسم البياني ، 'أ' ، 'و')) ؛ / / الإخراج: 1
تتيح الطرق الموضحة أعلاه حساب عدد المسارات في الرسم البياني بكفاءة. يعتمد اختيار الطريقة على المهمة المحددة وهيكل الرسم البياني. من المهم أن تضع في اعتبارك أنه عند العمل مع الرسوم البيانية الكبيرة ، يمكن أن تكون بعض الطرق باهظة الثمن من الناحية الحسابية وتتطلب التحسين.
طريقة عدد من القمم والحواف
تعد طريقة عدد الرؤوس والحواف إحدى الطرق الرئيسية لتحديد عدد المسارات في الرسم البياني. يعتمد على حساب عدد المسارات باستخدام عدد الرؤوس والحواف.
لاستخدام طريقة عدد الرؤوس والحواف ، تحتاج إلى معرفة العدد الإجمالي للرؤوس والحواف في الرسم البياني. إذا كان الرسم البياني قد وجه الحواف ، فمن الضروري أن تأخذ في الاعتبار اتجاهها عند حساب المسارات.
يمكن تقسيم تطبيق طريقة عدد الرؤوس والحواف إلى حالتين:
- إذا لم يكن للرسم البياني دورات ، فيمكن العثور على العدد الإجمالي للمسارات بواسطة الصيغة: إجمالي عدد المسارات = ن * (ن — 1) / 2 ، أين ن هو عدد الرؤوس في الرسم البياني.
- إذا كان الرسم البياني يحتوي على دورات ، فيمكن العثور على العدد الإجمالي للمسارات بضرب عدد الرؤوس في عدد الدورات: إجمالي عدد المسارات = ن * عدد الدورات.
مثال على استخدام طريقة عدد الرؤوس والحواف:
| الرسم البياني | عدد القمم | عدد الحواف | العدد الإجمالي للمسارات |
|---|---|---|---|
| هو 5 | 7 | 17 |
في هذا المثال ، يحتوي الرسم البياني على 5 رؤوس و 7 حواف. لذلك ، سيكون العدد الإجمالي للمسارات 17.
طريقة مصفوفة الجوار
طريقة مصفوفة الجوار هي إحدى الطرق الرئيسية لحساب عدد المسارات في الرسم البياني. يعتمد على تمثيل الرسم البياني كمصفوفة مجاورة ، حيث يشير كل عنصر من عناصر المصفوفة إلى ما إذا كانت هناك حافة بين الرؤوس المقابلة.
الخوارزمية:
- قم بإنشاء مصفوفة مجاورة للحجم ن س ن ، أين ن هو عدد الرؤوس في الرسم البياني.
- املأ مصفوفة الجوار بالقيم المكتوبة بواسطة حواف الرسم البياني. إذا كانت هناك حافة بين القمم أنا و ي ، فإن عنصر مصفوفة الجوار مع الفهارس (أنا ، ي) سيكون مساويا لـ 1 ، وإلا سيكون 0.
- ارفع مصفوفة الجوار إلى قوة ك ، أين ك هو طول المسار الذي يجب حساب عدد الخيارات من أجله.
- تلخيص جميع عناصر مصفوفة المجاورة الناتجة للحصول على العدد الإجمالي للمسارات.
مثال:
لنفترض أن لدينا رسما بيانيا يحتوي على 4 رؤوس والحواف التالية:
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
لحساب عدد مسارات الطول 2 ، من الضروري تربيع مصفوفة الجوار:
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 1 | 2 | 1 |
| 2 | 1 | 2 | 1 | 1 |
| 3 | 2 | 1 | 2 | 1 |
| 4 | 1 | 1 | 1 | 1 |
بتلخيص جميع عناصر مصفوفة الجوار الناتجة ، نحصل على العدد الإجمالي للمسارات بطول 2-12.
وبالتالي ، تسمح لك طريقة مصفوفة الجوار بحساب عدد المسارات في الرسم البياني بكفاءة بناء على مصفوفة الجوار.
أمثلة على حل مشكلة عد المسارات في الرسم البياني
يمكن حل مشكلة عد المسارات في الرسم البياني بطرق مختلفة ، اعتمادا على بنية الرسم البياني ومتطلبات العد. لنلق نظرة على بعض الأمثلة لحل هذه المشكلة:
- طريقة عبور الرسم البياني في العمق (العمق-البحث الأول)
- يتم تحديد الرأس الأولي
- بشكل متكرر نذهب عميقا في الرسم البياني ، وزيارة القمم المجاورة
- إذا تم الوصول إلى قمة الرأس النهائية ، فإننا نزيد عداد المسار
- نعود ومواصلة الزحف ، واختيار القمم المجاورة الأخرى
- اتساع-طريقة البحث الأولى
- يتم تحديد الرأس الأولي
- يضاف إلى قائمة الانتظار
- في حين أن قائمة الانتظار ليست فارغة ، ونحن استخراج قمة الرأس من قائمة الانتظار والنظر في جيرانها
- إذا تم الوصول إلى قمة الرأس النهائية ، فإننا نوقف الزحف
- كرر الخطوات مع القمم المجاورة السابقة للعثور على جميع المسارات الممكنة
- طريقة البرمجة الديناميكية
- تحديد الحالات الأساسية للرؤوس الأولية والنهائية
- باستخدام علاقة التكرار ، احسب عدد المسارات لكل رأس
- إرجاع عدد المسارات للرؤوس المحددة
هذه الطريقة مناسبة لحساب المسارات في الرسم البياني عندما تحتاج إلى العثور على جميع المسارات الممكنة من رأس إلى آخر. تعمل خوارزمية عبور الرسم البياني بعمق على النحو التالي:
ميزة هذه الطريقة هي أنها تجد جميع المسارات الممكنة بين رأسين معينين. ومع ذلك ، قد تكون هذه الطريقة غير فعالة للرسوم البيانية الكبيرة.
هذه الطريقة مناسبة لحساب أقصر المسارات في الرسم البياني. تعمل خوارزمية البحث الاتساع أولا على النحو التالي:
تعثر هذه الطريقة على جميع المسارات الأقصر بين رؤوس معينة ، ولكنها لا تضمن العثور على جميع المسارات الممكنة.
هذه الطريقة مناسبة لحساب المسارات في رسم بياني مع قيود محددة ، على سبيل المثال ، قيود على طول المسار أو وجود رؤوس معينة في المسار. يمكن تطبيق خوارزمية البرمجة الديناميكية بالشكل التالي:
كل من هذه الأساليب لها مزاياها وقيودها. يعتمد اختيار طريقة لحل مشكلة عد المسارات في الرسم البياني على متطلبات العد وهيكل الرسم البياني.
سؤال وجواب
ما هي الطرق التي يمكن استخدامها لحساب عدد المسارات في الرسم البياني?
هناك عدة طرق لحساب عدد المسارات في الرسم البياني. واحدة من أبسط الطرق هي طريقة العد العودية. طريقة أخرى هي طريقة جبر المصفوفة. هناك أيضا طرق تعتمد على البحث عن الاتساع أولا والبحث عن العمق أولا.
كيف يمكنني استخدام طريقة العودية لحساب عدد المسارات في الرسم البياني?
لاستخدام طريقة العودية لحساب عدد المسارات في الرسم البياني ، يمكنك تحديد الحالة الأساسية ، أي الحالة التي تم فيها العثور على المسار بالفعل ، واستدعاء الدالة بشكل متكرر لكل رأس من الجار حتى يتم الوصول إلى الحالة الأساسية.
كيف تعمل طريقة جبر المصفوفة لحساب عدد المسارات في الرسم البياني?
تمثل طريقة جبر المصفوفة لحساب عدد المسارات في الرسم البياني الرسم البياني كمصفوفة مجاورة ثم ترفع هذه المصفوفة إلى قوة ن ، أين ن هو عدد الرؤوس في المسار. وبالتالي ، فإن القيمة في الموضع (أنا ، ي) للمصفوفة الناتجة ستكون عدد المسارات من قمة الرأس أنا إلى قمة الرأس ي.