أفضل طريقة لاختبار الوصول إلى إجمالي

Question

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

1--2
   |
3--4

عكس:

1--2

3--4

أنا مقتنع أن هذا النوع من اختبار الواجهة يمكن أن يكون من المتوقع من حيث مشكلة الغلاف الدقيق, ومع ذلك، لا يمكنني أن أبدو ذهني ملفوفا حول كيفية القيام بذلك. هل لدى أي شخص أي مؤشرات أو وثائق أو مواقع ويب، وما إلى ذلك، حول كيفية القيام بذلك؟ ومن الأمثلة على ذلك قيمة للغاية.

تحديث: خانى جهلي، كما يبدو أن هناك خوارزميات أكثر كفاءة لهذا النوع من الاختبار. إذا كان لديك واحدة، يرجى توجيهي إليها.

Answer 1

• ابدأ من أي عقدة وقم بعمق / اتساع أول اجتياز
• عدد عدد العقدة المتزايدة (بالطبع، لا تفضل بزيارة أي عقدة مرتين!)
• قارن عدد العد مع العدد الإجمالي

Answer 2

هناك أيضا خوارزمية سريعة (ولكن معقدة) لصيانة الاتصال بشكل حيوي (أي ضمن إدراج الحافة / الحذف)، كما هو موضح في هذه الورقة: خوارزميات بولي لوغاريتمي حتمية تماما للاتصال، الحد الأدنى للشجرة الممتدة، 2-حافة، وثنية

الفكرة الأساسية هي الحفاظ على شجرة ممتد. الحالات السهلة تقوم بإدراج حافة وحذف حافة شجرة غير ممتد. المشكلة هي عند حذف حافة شجرة ممتد، لأنه الآن لا يوجد اتصال مضمون - يتعين علينا البحث عن طريق بديل بكفاءة لتوصيل الأجزاء المكسورة، وإلا يتم قطع اتصال الرسم البياني.