إيجاد جميع القمم في الرسم البياني بدرجة أصغر من جيرانها

Question

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

Answer 1

ربما "يبدو أن هذا قد يستغرق وقتًا طويلاً للغاية"، ولكن هناك طريقة أفضل لمعرفة ذلك :-)

لنفترض أنك قمت بتخزين الرسم البياني الخاص بك كقائمة مجاورة.للعثور على المجموعة التي تبحث عنها، عليك بالضرورة أن تنظر إلى جميع الحواف، لذلك لدينا الأدنى من Ω(|E|) للخوارزمية.يستغرق العثور على درجة كل قمة وقتًا O(|E|) (لأنك تنظر إلى كل حافة مرة واحدة بالضبط؛والدليل الآخر هو استخدام حقيقة أن ∑d(v)=2|E|).إن مقارنة درجة كل قمة مع جميع جيرانها تستغرق أيضًا وقتًا O(|E|) فقط (مرة أخرى، لكل حافة، يمكنك إجراء مقارنة واحدة فقط).وهذا يعني أن الخوارزمية الخاصة بك تعمل في وقت O(|E|) (حوالي 2|E| "خطوات"، ولكن العدد الدقيق لتعليمات وحدة المعالجة المركزية يعتمد على التنفيذ الخاص بك)، وهو ما يلبي الحد الأدنى.وبالتالي فإن خوارزمية "القوة الغاشمة" الخاصة بك، في أسوأ الحالات، هي في الأساس (تصل إلى ثابت صغير) بأسرع ما يمكن, ، لذلك لا يستحق المزيد من التحسين.

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

Answer 2

وتعليق واحد - <م> إذا كنت تعمل مع الرسوم البيانية غير موجهة (شكرا، براين R . بوندي )، مرة واحدة كنت قد قررت أن قمة الرأس على درجة أقل من ذلك من جميع جيرانها، لا تحتاج إلى التحقق من الجيران، لأن أيا منهم لن يكون تلك الممتلكات. النظر في استخدام هذه المعرفة لمساعدتك وتسريع الامور.

Answer 3

وأتصور نهج الجشع لبياني صليات كما يلي:

let Q = all nodes which haven't been checked (initialize all V)
let Q* = all nodes which satisfy the required condition (initialize to empty)
start with an arbitrary node, v in Q
while Q is not empty
    let minDeg be the minimum degree of all v's neighbors
    if degree(v) < minDeg
        add v to Q*
        remove all neighbors of v from Q
        remove v from Q
        set v = new arbitrary node, v in Q
    else
        remove v from Q
        set v = v's neighbor in Q of minimum degree

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

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