قم بإنشاء عدد من الحواف بين عقدتين

Question

لقد قمت بإنشاء هذا الحد الأدنى من الأشجار الممتدة باستخدام خوارزمية Kruskal ولدي مسارات توليد صعوبة بين العقدتين.هل يمكن لشخص مساعدتي مع pseudocode؟حاولت استخدام قائمة مجاورة ومصفوفة مجاورة giveacodicetagpre.

Answer 1

إذا كنت تريد فقط أي مسار بين عقدتين ، فإن Breadth First Search سيفي بالغرض ، وسيولد أقصر مسار (لأنه يمثل الحد الأدنى من الشجرة الممتدة).

Answer 2

تمتد الأشجار، بحكم التعريف، لا تملك دورات (أو حلقات)، لذلك في معظمها، يمكنك فقط الحصول على مسار واحد فقط (I.E. ليس "مسارات"، الجمع) بين العقدتين.

ربما أنا لا أفهم السؤال.هل تحاول أن تجد كيف ترتبط اثنين من العقدتين في شجرة الخاص بك؟

إذا كان الأمر كذلك، فإنه يبدو لي مثل أبسط القوة الغاشمة على هذا، حيث ستتبع فقط من نقطة واحدة على طول الحواف المحتملة، ربما عن طريق دفع وإرطف إمكانيات من كومة، ستكون أسوأ الحالات O (حواف)وقت التشغيل، الذي سيكون تافهة مقارنة بخوارزمية كروسكال. هل تحتاج إلى شيء أسرع؟