خوارزميات الرسوم البيانية

13. خوارزميات الرسوم البيانية

نعرض في هذا الفصل خوارزميات الرسوم البيانية. هذه الخوارزميات مستقلة عن بنية بيانات الرسم البياني الأساسية. ويمكن استخدامها، على وجه الخصوص، مع جميع بنى الرسوم البيانية الواردة في الفصل 7. فيما يلي، سنعتبر معطاةً وحدة G يتضمّن توقيعها على الأقل الأنواع والدوال والوحدات الخاصة بالبرنامج 98. الرسوم البيانية من النوع graph، ورؤوسها من النوع vertex. الدالة iter_vertex تمرّ على رؤوس رسم بياني معطى، وتطبّق دالةً تُمرَّر كوسيط على كل واحد منها. والدالة iter_succ تمرّ على الرؤوس اللاحقة (successors) لرأس معطى. وتوفّر الوحدة H بنية جدول تجزئة (hash table) مفاتيحها رؤوس.

13.1 البحث بالعرض أولاً

أول عملية اجتياز نعرضها تُسمّى البحث بالعرض أولاً(BFS). وهي تتمثل في استكشاف الرسم البياني بالتحرّك نحو الخارج «في دوائر متحدة المركز»، انطلاقاً من رأس معيّن s يُسمّى الجذر. نمرّ أولاً على الرؤوس التي تبعد قوساً واحداً بالضبط عن الجذر s، ثم على تلك التي تبعد قوسين، وهكذا. خُذ، على سبيل المثال، الرسم البياني الواقع على اليسار في الشكل 13.1. بدءاً من الرأس 5، نزور أولاً الرأسين 4 و1، وهما مرتبطان مباشرةً بالرأس 5. ثم نزور الرؤوس 0 و6 و2، يليها الرأس 7، وأخيراً الرأس 3. ويظهر الرسم البياني، مع المسافات إلى الجذر مكتوبةً كأُسُس، على اليمين.

الشكل 13.1: البحث بالعرض أولاً في رسم بياني.

نكتب البحث بالعرض أولاً في صورة دالة iter_bfs تأخذ كوسائط رسمًا بيانيًا g وجذرًا s ودالةً f ستُطبَّق على عناصر g أثناء اكتشافها. نبدأ بإنشاء جدول تجزئة يحتوي على الرؤوس المكتشَفة سابقًا بواسطة الاجتياز.

  let iter_bfs f g s =
    let visited = H.create () in

يعتمد البحث نفسه على استخدام طابور (queue) تُدرَج فيه الرؤوس أثناء اكتشافها. والفكرة أنه، في أي لحظة زمنية، سيحتوي الطابور على الرؤوس الواقعة على مسافة d من الجذر، تليها الرؤوس الواقعة على مسافة d + 1:

وهذا هو التجسيد لمفهومنا عن «الدوائر متحدة المركز»، وبشكل أدقّ للدائرتين المتتاليتين قيد الاعتبار. وهذه الخاصية جوهرية لصحة البحث بالعرض أولاً^[1]. وهنا نستخدم الوحدة Queue لتنفيذ الطابور. وهو يحتوي في البداية على الجذر فقط. ومن المفيد كتابة دالة add تُضيف رأسًا في آن واحد إلى جدول التجزئة وإلى الطابور. نبدأ باستخدامها على الجذر s.

    let queue = Queue.create () in
    let add w = H.add visited w (); Queue.add w queue in
    add s;

وثمة خاصية مهمة أخرى هي أنّ كل رأس موجود في الطابور موجود أيضًا في الجدول visited، وهذا ما تضمنه الدالة add بطريقة واضحة. ونستخدم حلقة لفحص الرؤوس بالترتيب الذي اكتُشفت به، إلى أن تُفحص جميع الرؤوس التي يمكن الوصول إليها من الجذر. وما دام الطابور غير فارغ، نستخرج العنصر الأول v من الطابور ونطبّق عليه الدالة الزائرة f.

    while not (Queue.is_empty queue) do
      let v = Queue.pop queue in
      f v;

لكل رأس لاحق (successor) w للرأس v لم يُعثَر عليه بعد، أي غير موجود في الجدول visited، نستخدم add لإضافته إلى كلٍّ من الطابور والجدول.

      iter_succ (fun w -> if not (H.mem visited w) then add w) g v
    done

وبذلك تكتمل حلقة while والدالة iter_bfs. ويُعطى الكود الكامل في البرنامج 99 أدناه.

ينطبق هذا الكود بالقدر نفسه على الرسوم البيانية غير الموجّهة والموجّهة. لاحظ أن بعض الرؤوس قد لا يكتشفها هذا الخوارزم. وهذه هي الرؤوس v التي لا يوجد مسار بينها وبين الجذر. بعبارة أخرى، يحدّد البحث بالعرض أولاً مجموعة الرؤوس التي يمكن الوصول إليها من الجذر، بل ويحدّد مسافتها الدنيا من الجذر بعدد الأقواس (انظر التمرين 13.1).

من السهل تحديد تعقيد البحث بالعرض أولاً. يُوضَع كل رأس في الطابور مرة واحدة على الأكثر، ومن ثُمَّ يُفحص مرة واحدة على الأكثر. ويُنظر إلى كل قوس مرة واحدة على الأكثر، عند فحص رأس بدايته. بالنسبة إلى رسم بياني فيه N رأسًا وE قوسًا، يكون التعقيد بالتالي O(N + E)، وهو أمثل. أما التعقيد في المكان فهو O(N)، لأن الطابور، شأنه شأن جدول التجزئة، قد يحتوي على (جميع) الرؤوس تقريبًا في أسوأ الحالات.

ثمة طريقة أخرى لتنفيذ البحث بالعرض أولاً، دون استخدام طابور. وكما لوحظ أعلاه، فإنّ للطابور بنية خاصة جدًا، إذ يحتوي على الرؤوس على مسافة d تليها الرؤوس على مسافة d + 1. ولذلك نرى أنّ بنية الطابور ليست ضرورية فعلًا. كل ما نحتاجه هو «دلوان»، أحدهما يحتوي على الرؤوس على مسافة d، والآخر على تلك على مسافة d + 1. ويمكننا تجسيدهما، مثلًا، باستخدام قوائم. وعندما ننتهي من الدلو d، نبادل الدلوين. وهذا لا يؤثّر في التعقيد.

13.2 البحث بالعمق أولاً

ثاني عملية اجتياز للرسم البياني نعرضها هي البحث بالعمق أولاً(DFS). وتستخدم خوارزمية تتبّع خلفي (backtracking): ما دمنا قادرين على اتّباع قوس، نفعل ذلك، وعندما يتعذّر ذلك، نتراجع. وكما في البحث بالعرض أولاً، نُعلّم الرؤوس أثناء اكتشافها، لتفادي الوقوع في حبس دورة. خُذ مثال الرسم البياني الواقع على اليسار في الشكل 13.2. نبدأ بحثًا بالعمق أولاً من الرأس 2. يخرج قوسان من هذا الرأس: 2 → 4 و2 → 5. نختار اعتباطًا النظر في القوس 2 → 5 أولاً، وبالتالي ننتقل إلى الرأس 5. لا يخرج أي قوس من 5،

لذلك لا يمكننا المواصلة. لذلك نتراجع إلى الرأس 2، وننظر في القوس الخارج الثاني، 2 → 4. ومن 4، لا يمكننا اتبّاع سوى القوس 4 → 3. وكذلك، من 3، لا يمكننا اتبّاع سوى القوس 3 → 1. ويخرج قوسان من الرأس 1: 1 → 0 و1 → 4. نختار اتبّاع القوس 1 → 4 أولاً. وهو يقود إلى رأس زُير سابقًا. لذلك نتراجع. وبالعودة إلى 1، ننظر في القوس الآخر، 1 → 0، الذي يقود إلى 0. ومن هناك، القوس الخارج الوحيد يقود إلى 3، وقد زُير هو أيضًا سابقًا. لذلك نعود إلى 0، ثم إلى 1، ثم إلى 3، ثم إلى 4، وأخيراً إلى 2. ويكتمل الاجتياز. وإذا أعدنا رسم الرسم البياني بترتيب اكتشاف الرؤوس مكتوبًا كأُسُس، نحصل على الرسم البياني على اليمين في الشكل 13.2.

الشكل 13.2: مثال على البحث بالعمق أولاً.

وكما في البحث بالعرض أولاً، سنستخدم جدول تجزئة يحتوي على الرؤوس المكتشَفة سابقًا.

  let iter_dfs f g s =
    let visited = H.create () in

يُكتب البحث بالعمق أولاً في صورة دالة محلية عودية visit تأخذ رأسًا v كوسيط. وكودها لا يزيد عن بضعة أسطر:

    let rec visit v =
      if not (H.mem visited v) then begin
        H.add visited v ();
        f v;
        iter_succ visit g v
      end

إذا كان الرأس v قد اكتُشف سابقًا، فلا شيء آخر يُفعل. وإلا، فإننا نُعلّمه ونزوره بالدالة f. ثم ننظر في كل رأس لاحق w، ونُشغّل عليه بشكل عودي بحثًا بالعمق أولاً. وثمة تفصيل جوهري: أضفنا v إلى الجدول visited قبلالنظر في رؤوسه اللاحقة. وهذا هو ما يمنعنا من الوقوع في حبس دورة. ولإنهاء الدالة iter_dfs، ليس علينا سوى استدعاء visit على الجذر s:

    in
    visit s

يُعطى الكود الكامل في البرنامج 100.

التعقيد هو O(N + E)، بالمنطق نفسه كما في حالة البحث بالعرض أولاً. أما تعقيد المكان فمنطقه أدقّ، إذ إنّ مكدّس الاستدعاءات العودية هو الذي يحتوي على الرؤوس قيد الزيارة، وهو الذي يلعب دور الطابور في البحث بالعرض أولاً. ولأنّ جميع الرؤوس قد تكون حاضرة في المكدّس أو جدول التجزئة في أسوأ الحالات، فإنّ تعقيد المكان هو O(N).

وكما في البحث بالعرض أولاً، يسمح لنا البحث بالعمق أولاً بتحديد مجموعة الرؤوس التي يمكن الوصول إليها من الجذر s. ويوضّح الشكل 13.3 مثالًا آخر، حيث يُشغَّل البحث بالعمق أولاً من الرأس 1. ولا يُكتشَف الرأسان 2 و5. وعلى وجه الخصوص، فإنّ البحث بالعمق أولاً، شأنه شأن البحث بالعرض أولاً، وسيلة لتحديد وجود مسار بين رأس معيّن، وهو الجذر، ورؤوس أخرى من الرسم البياني. وإذا كان ذلك هو الهدف الوحيد (إذا لم تكن المسافة الدنيا تهمّنا، مثلًا)، فإنّ البحث بالعمق أولاً يكون عادةً أكثر كفاءة. فاستهلاكه للذاكرة (أي مكدّس الاستدعاءات) يكون كثيرًا ما أدنى من استهلاك البحث بالعرض أولاً. والمثال النموذجي هو الشجرة، إذ يقتصر استهلاك الذاكرة على ارتفاع الشجرة في حالة البحث بالعمق أولاً، لكنه قد يبلغ حجم الشجرة بأكملها في حالة البحث بالعرض أولاً. وللبحث بالعمق أولاً تطبيقات كثيرة أخرى تقع خارج نطاق هذا الكتاب. انظر، على سبيل المثال، Introduction to Algorithms [7].

الشكل 13.3: بحث بالعمق أولاً آخر.

13.3 المسار الأقصر

ننظر هنا في رسوم بيانية موسومة أقواسها بأوزان (تمثّل مسافات، مثلًا). ونبحث عن المسار الأقصر بين رأسين، حيث لا يكون الطول عدد الأقواس بل مجموع الأوزان على طول المسار. وهكذا، إذا نظرنا في الرسم البياني الموزون في الشكل 13.4، فإنّ المسار الأقصر من الرأس 2 إلى الرأس 0 طوله 5. وهذا هو المسار 2 → 4 → 3 → 1 → 0، وهو أقصر من المسار 2 → 1 → 0 الذي طوله 6، حتى إن كان الأخير يحتوي على أقواس أقل. وبالمثل، فإنّ المسار الأقصر من الرأس 2 إلى الرأس 5، مرورًا بالرأس 4، طوله 2.

الشكل 13.4: مثال على رسم بياني موزون.

وكما في البحث بالعرض والعمق أولاً، نعتبر معطىً رأسًا s نبحث منه عن تحديد المسارات الأقصر إلى الرؤوس الأخرى. ونحتاج كذلك إلى وزن كل قوس. ومن الممكن تعديل بنية الرسم البياني لتضمين ذلك. لكننا هنا نعتبر معطاةً دالة وزن weight من النوع التالي، حيث الأوزان من النوع float:

  val weight: graph -> vertex -> vertex -> float

لن تُستدعى هذه الدالة إلا بالوسائط g وx وy إذا وُجد قوس بين x وy في الرسم البياني g.

نعرض خوارزميتين لحلّ المسألة. الأولى، خوارزمية ديكسترا (Dijkstra)، تفترض أنّ الأوزان غير سالبة دائمًا. والثانية، خوارزمية بلمان-فورد (Bellman-Ford)، لا تتضمّن أي افتراض من هذا القبيل بشأن الأوزان.

خوارزمية ديكسترا

خوارزمية ديكسترا تعميم للبحث بالعرض أولاً. وهنا أيضًا نتقدّم في «دوائر متحدة المركز». والفرق أنّ أنصاف أقطار هذه الدوائر تمثّل المسافة بدلالة الوزن الكلي لا عدد الأقواس. وهكذا، في المثال أعلاه، بدءًا من الجذر 2، نصل أولاً إلى الرؤوس على مسافة 1 (وهو 4)، ثم إلى تلك على مسافة 2 (وهما 3 و5)، ثم إلى تلك على مسافة 3 (وهو 1)، وأخيراً إلى تلك على مسافة 5 (وهو 0). ومن التعقيدات المحتملة أن نصل إلى رأس على مسافة معيّنة (على سبيل المثال، الرأس 5 عبر القوس 2 → 5)، ثم نجد لاحقًا مسارًا أقصر باتّباع أقواس مختلفة (على سبيل المثال، 2 → 4 → 5). ولم يعد الطابور كافيًا كما كان في البحث بالعرض أولاً. بل سنستخدم طابور أولوية (priority queue) (انظر الفصل 6). وسيحتوي طابور الأولوية على الرؤوس المكتشَفة بالترتيب حسب المسافة من الجذر. وعند العثور على مسار أفضل إلى رأس،

يُعاد إدراج الرأس في الطابور بأولوية أعلى، أي مسافة أقصر[^2].

نصف الآن كود خوارزمية ديكسترا. ولتنفيذ طابور الأولوية، نفترض وجود دالة رافدة (functor) اسمها PriorityQueue، مُعامَلة بنوع t مزوّد بترتيب كلي. (وقد عُرضت مثل هذه الدوال الرافدة في الفصل 6.) وهنا سيكون النوع t هو نوع الأزواج (v,d)، حيث v رأس وd مسافته من الجذر. والترتيب المعتمد على هذه الأزواج هو الناتج عن مقارنة المسافات. ونُعرِّف الوحدة التالية:

  module VertexDistance = struct
    type t = vertex * float
    let compare (_, d1) (_, d2) = Stdlib.compare d1 d2
  end

ولم يتبقَّ سوى تطبيق الدالة الرافدة PriorityQueue على الوحدة VertexDistance، أي:

  module P = PriorityQueue(VertexDistance)

نفترض هنا أنّ الوحدة P توفّر دالة create لبناء طابور أولوية جديد، ودالة add لإضافة عنصر، ودالة extract_min التي تحذف وتُعيد أصغر عنصر بالنسبة إلى الترتيب المعرَّف بالدالة compare.

نصل الآن إلى كود الخوارزمية نفسها. نكتبها في صورة دالة dijkstra تأخذ كوسائط رسمًا بيانيًا g وجذرًا s ودالةً f. وستُطبَّق الدالة f على عناصر g عند تحديد مسافتها الدنيا إلى s، حيث يُمرَّر الرأس إلى f كوسيط أول، ومسافته كوسيط ثانٍ. نبدأ بإنشاء جدول تجزئة يحتوي على الرؤوس التي وصل إليها الاجتياز سابقًا.

  let rec dijkstra f g s =
    let visited = H.create () in

نُنشئ أيضًا جدول تجزئة، distance، وطابور الأولوية، queue. وسيحتوي جدول التجزئة على المسافة المعروفة حاليًا لكل رأس.

    let distance = H.create () in
    let queue = P.create () in

من الملائم تعريف دالة add تُضيف رأسًا إلى بنيتي البيانات هاتين في الوقت نفسه. ونبدأ بتطبيقها على الجذر s.

    let add v d = H.replace distance v d; P.add queue (v, d) in
    add s 0.;

سنرى أدناه سبب تفضيل H.replace على H.add. ثم نواصل بحلقة ما دام الطابور غير فارغ.

    while not (P.is_empty queue) do

نستخرج العنصر الأول من الطابور، u، مع المسافة إلى الجذر du. وإذا كان الرأس u موجودًا في visited سابقًا، فقد حدّدنا مسافة s إلى u بالفعل، ولم يعد هناك ما يُفعل.

      let (u, du) = P.extract_min queue in
      if not (H.mem visited u) then begin

قد تحدث هذه الحالة فعلًا عند العثور على مسار أول ثم العثور لاحقًا على مسار آخر أقصر. وحينئذٍ يمرّ الأخير قبل الأول في طابور الأولوية. وعندما يخرج المسار الأطول أخيرًا من الطابور، ينبغي تجاهله. وإذا كان الرأس غير موجود في visited، فذلك يعني أننا وجدنا للتوّ مسارًا أقصر من s إلى u، وهذا ما نشير إليه بإضافة u إلى الجدول visited وبتطبيق الدالة الزائرة f على u وdu.

        H.add visited u ();
        f u du;

بعد ذلك، سنفحص جميع الأقواس الخارجة من u. ولكل قوس u → v، تكون المسافة إلى v الناتجة من اتبّاع القوس المقابل هي مجموع المسافة du ووزن القوس، أي weightuv. وتُحتمَل عدة سيناريوهات بالنسبة إلى الرأس v. إما أن يكون الوصول إليه للمرة الأولى، أو أنه كان موجودًا في distance سابقًا. وفي الحالة الأخيرة، قد نكون قد خفّضنا المسافة إلى v بالمرور عبر u. وإذا كان الأمر كذلك، كفى استخدام الدالة add لتحديث الجدولين. ونعالج كل رأس لاحق v في الدالة visit أدناه:

        let visit v =
          let d = du +. weight g u v in
          if not (H.mem distance v) || d < H.find distance v then
            add v d

ولم يتبقَّ سوى تطبيق هذه الدالة على جميع الأقواس الخارجة من u، وهو ما يُنهي جسم حلقة while.

        in
        iter_succ visit g u
      end
    done

وبعد الخروج من حلقة while، يكون قد زُير كل رأس يمكن الوصول إليه من s. ويُعطى الكود الكامل في البرنامج 101 أعلاه.

ويُظهر الشكل 13.5 نتيجة خوارزمية ديكسترا على الرسم البياني المعطى في المثال السابق، مع 2 جذرًا. وقد رُسم الرسم البياني بالمسافات النهائية المتحصَّلة لكل رأس مكتوبةً كأُسُس. وفي هذا المثال، وُصل إلى جميع الرؤوس بواسطة الاجتياز. أما في البحث بالعرض والعمق أولاً، فليس الأمر كذلك دائمًا: فلا يُوصل إلا إلى الرؤوس التي يوجد لها مسار من الجذر.

الشكل 13.5: نتيجة خوارزمية ديكسترا.

التعقيد

لنقيّم كلفة خوارزمية ديكسترا في أسوأ الحالات. قد يحتوي طابور الأولوية على ما يصل إلى E عنصر، لأنّ الخوارزمية تمرّ على كل قوس مرة واحدة على الأكثر، وكل قوس قد يؤدي إلى إدراج عنصر في الطابور. وبافتراض أنّ عمليتي طابور الأولوية add وextract_min لهما كلفة لوغاريتمية (كما هو الحال في طوابير الأولوية الموصوفة في الفصل 6)، فستكون لكل عملية على الطابور كلفة O(log E)، أي O(log N)، بما أنّ E ≤ N2. والكلفة الكلية بالتالي هي O(E log N).

خوارزمية بلمان-فورد

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

تتضمّن هذه الخوارزمية تكرار العملية التالية N مرة: انظر في كل قوس u → v من الرسم البياني وحدّد ما إذا كان سلوكه سيقلّل المسافة المعروفة حاليًا بين المصدر وv. والفكرة أنّ المسار الأقصر بين s وv لا يمكن أن يحتوي على أكثر من N − 1 قوسًا، وإلا لاحتوى هذا المسار على دورة، يمكننا حذفها من المسار إذا كان وزنها غير سالب.

الوزن. ولهذا تكفي N تكرارات.

نكتب الآن كود خوارزمية بلمان-فورد. نبدأ بتعريف دالة iter_edge تمرّ على جميع أقواس رسم بياني g.

  let iter_edge f g =
    iter_vertex (fun u ->
      iter_succ (fun v -> f u v (weight g u v)) g u) g

لكل قوس u → v، تطبّق الدالة iter_edge الدالة f على الرأسين u و v، وعلى مسافة القوس u → v المعطاة بالدالة weight.

وتأخذ الدالة bellman_ford رسمًا بيانيًا g ورأس جذر s كوسيطين. وهي تبدأ بإنشاء جدول تجزئة h يحتوي على المسافات المعروفة لكل رأس.

  let bellman_ford g s =
    let h = H.create () in

نبدأ بتهيئة هذا الجدول، بإعطاء s المسافة 0 وإعطاء كل رأس آخر مسافة لانهائية.

    iter_vertex (fun v -> H.add h v max_float) g;
    H.add h s 0.;

نستخدم هنا الثابت max_float لتمثيل مسافة لانهائية. ثم نكرّر العملية التالية N − 1 مرة: نفحص كل قوس، باستخدام حلقة for والدالة iter_edge.

    for i = 1 to nb_vertex g - 1 do
      iter_edge (fun u v w ->

لكل قوس u → v، نحسب المسافة d من الجذر إلى v الناتجة عن سلوك هذا القوس. وإذا كانت أصغر من أفضل مسافة معروفة حاليًا، نسجّلها.

        let d = H.find h u +. w in
        if d < H.find h v then H.replace h v d

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

    done;
    iter_edge (fun u v w ->
      if H.find h u +. w < H.find h v then
        raise NegativeCycle

وبذلك تكتمل خوارزمية بلمان-فورد. ويمكننا إرجاع الجدول h الذي يعطي مسافة كل رأس إلى المصدر. وهذا ما يُفعل في البرنامج 102.

الشكل 13.6: توضيح لخوارزمية بلمان-فورد.

نوضّح خوارزمية بلمان-فورد بمثال. خُذ الرسم البياني في الشكل 13.6، الذي نبحث فيه عن تحديد المسافات من الرأس 5. والجدول الواقع على يمين الرسم البياني يعطي المسافة المكتشَفة لكل رأس بعد كل خطوة. وفي البداية، تكون جميع الرؤوس على مسافة لانهائية، إلا الجذر 5. وفي كل خطوة، نفترض أنّ الرؤوس تُجتاز بترتيب ترقيمها. ونلاحظ، على سبيل المثال، أنّ المسافة إلى الرأس 2 تأخذ أولاً القيمة 3 (القوس 5 → 2)، ثم القيمة 2 (بالمرور عبر الرأس 1)، وأخيراً القيمة -2 (بالمرور عبر الرأسين 4 و1). وبعد ذلك، لا تتغيّر بعد الآن. وبشكل أعمّ، نلاحظ هنا أنّ أياً من المسافات لا تتحسّن خلال الخطوتين الأخيرتين من الخوارزمية. وعلى وجه الخصوص، لا توجد دورة سالبة.

التعقيد

من السهل تقييم كلفة خوارزمية بلمان-فورد في أسوأ الحالات. فنحن ننفّذ N مرورًا بالضبط، ويفحص كل مرور كل قوس من الأقواس E مرة واحدة ومرة فقط. ولذلك يكون التعقيد O(EN)، أي O(N3) في أسوأ الحالات. أما في الممارسة، فيمكننا تحسين الأداء بشكل ملحوظ بملاحظة أنّ كثيرًا من الأقواس تُفحص بلا داعٍ عندما لا تكون المسافة من الجذر إلى الرأس البداية قد تغيّرت. ومن التحسينات البسيطة الأخرى التوقّف بمجرّد أنّ مرورًا لم يحسّن أيًّا من المسافات. لكنّ التعقيد في أسوأ الحالات يبقى، مع ذلك، هو نفسه.

13.4 الشجرة الممتدة الدنيا

ننظر هنا في رسم بياني غير موجّه موسومة أقواسه بأوزان. ونفترض أيضًا أنّ الرسم البياني متّصل، أي أنّ كل زوج من الرؤوس مرتبط بمسار. والشجرة الممتدة(spanning tree) مجموعة جزئية من الأقواس لا تحتوي على دورة وتربط جميع الرؤوس معًا. ومن السهل إقناع أنفسنا بوجود مثل هذه الشجرة. فمثلًا، سينتج بحث بالعمق أولاً يبدأ من رأس اعتباطي شجرةً كهذه: وهي تتكوّن من جميع الأقواس التي أدّت إلى اكتشاف رأس جديد.

نبحث بعد ذلك في مسألة إيجاد شجرة ممتدة وزنها الكلي أدنى ما يمكن. ونعرض هنا حلًّا يُعرف بـخوارزمية كروسكال(Kruskal). وتتضمّن هذه الخوارزمية اجتياز الأقواس بترتيب تصاعدي للوزن. ولكل قوس u − v، نحدّد ما إذا كانت إضافة القوس إلى مجموعة الأقواس المختارة سابقًا لتكوين الشجرة الممتدة تُنشئ دورة. فإن كان الأمر كذلك، نتجاهل القوس. وإلا، نختاره. وبعد فحص جميع الأقواس، تشكّل مجموعة الأقواس المختارة شجرة ممتدة دنيا (انظر التمرينين 13.24 و13.25).

ولتنفيذ هذه الخوارزمية، نحتاج إلى إيجاد وسيلة فعّالة لتحديد ما إذا كان اختيار قوس جديد يُدخل دورة بين الأقواس المختارة سابقًا. ولحسن الحظ، يوجد حلّ بسيط لهذه المسألة، في صورة بنية المجموعات المنفصلة المدروسة في الفصل 8. ففي الواقع، يكفي بناء بنية أوّلية يكون فيها كل رأس صنفًا قائمًا بذاته. ولكل قوس مختار u − v، ندمج صنفي u وv. وهذا يجسّد وجود مسار الآن بين كل زوج من الرؤوس في الصنف الجديد. ولاختبار ما إذا كان قوس يُدخل دورة، يكفي بالتالي اختبار ما إذا كان طرفاه ينتميان إلى الصنف نفسه.

نكتب الآن كود خوارزمية كروسكال، في صورة دالة spanning_tree تأخذ رسمًا بيانيًا كوسيط وتُعيد شجرة ممتدة دنيا في صورة قائمة أقواس. ونعتبر معطاةً وحدة UF لبنية المجموعات المنفصلة (انظر الفصل 8)، بالتوقيع التالي:

  module UF: sig
    val create : vertex list -> t
    val find : t -> vertex -> vertex
    val union : t -> vertex -> vertex -> unit
  end

نفترض وجود دالة vertices تُعيد قائمة رؤوس رسم بياني. ومن السهل الحصول على دالة كهذه من iter_vertex. وبالمثل، نفترض وجود دالة edges تُعيد قائمة جميع أقواس رسم بياني، حيث يكون كل قوس ثلاثية (x,y,w)، فيها w وزن القوس x − y. وهنا أيضًا، من السهل الحصول على هذه الدالة من iter_edge والدالة weight.

ويبدأ كود خوارزمية كروسكال بإنشاء بنية union-find انطلاقًا من قائمة رؤوس الرسم البياني:

  let spanning_tree g =
    let uf = UF.create (vertices g) in

ثم نرتّب قائمة أقواس الرسم البياني بترتيب تصاعدي للوزن، باستخدام دالة المكتبة List.sort. والمقارنة المستخدمة هنا هي مقارنة الأوزان، بالترتيب المعتاد على أعداد الفاصلة العائمة، أي Stdlib.compare.

    let compare (_,_,w1) (_,_,w2) = Stdlib.compare w1 w2 in
    let edges = List.sort compare (edges g) in

وتُخزَّن قائمة الأقواس المختارة لتكوين الشجرة الممتدة في مرجع محلي st.

    let st = ref [] in

ثم نكتب دالة cover تفحص قوسًا (u,v,w) وتحدّد ما إذا كان ينبغي اختياره. ولذلك، نقارن صنفي الرأسين u وv باستخدام الدالة UF.find. وإذا كانا مختلفين، نضيف القوس إلى القائمة st وندمج الصنفين، باستخدام الدالة UF.union.

    let cover ((u, v, w) as e) =
      if UF.find uf u <> UF.find uf v then begin
        UF.union uf u v;
        st := e :: !st
      end

وأخيراً، لم يتبقَّ سوى فحص كل قوس من القائمة edges بهذه الدالة، ثم إرجاع القائمة الناتجة.

    in
    List.iter cover edges;
    !st

ويُعطى كود خوارزمية كروسكال في البرنامج 103.

نوضّح خوارزمية كروسكال بمثال. خُذ الرسم البياني الواقع في أعلى يسار الشكل 13.7. وتُنظر الأقواس بترتيب تصاعدي للوزن، كما هو معروض في الجدول على يمين الشكل. ولكل قوس، نبيّن ما إذا كان مختارًا (عمود «أُضيف») والتقسيم الناتج في بنية union-find. والشجرة الممتدة المتحصَّل عليها في النهاية موضّحة في أسفل يسار الشكل. ووزنها الكلي -2. ومن المهم ملاحظة أنّ الأقواس ذات الوزن نفسه قد تُنظر بأي ترتيب. وهكذا، نظرنا هنا في القوس 0 − 1 قبل القوس 1 − 4، لكن كان بإمكاننا أيضًا فعل العكس. وكانت الشجرة الممتدة ستختلف، لكن وزنها الكلي كان سيظل هو نفسه.

الشكل 13.7: توضيح لخوارزمية كروسكال.

وثمة عدد من التنويعات والتحسينات الممكنة. فالتمرين 13.26 مثلًا يقترح قطع اجتياز الأقواس بمجرّد اختيار N − 1 قوسًا. وبالمثل، يقترح التمرين 13.27 استخدام طابور أولوية بدلًا من خوارزمية ترتيب. وعلى أي حال، تبقى الفكرة الجوهرية استخدام بنية بيانات المجموعات المنفصلة.

التعقيد

تنقسم كلفة خوارزمية كروسكال بين كلفة ترتيب مجموعة الأقواس E وكلفة فحص كل قوس. والكلفة الأولى هي O(E log E) في أسوأ الحالات، إذا استخدمنا خوارزمية ترتيب ذات تعقيد أمثل (انظر الفصل 12). والكلفة الثانية هي O(E) إذا اعتبرنا أنّ العمليات على بنية union-find ذات زمن ثابت (انظر الفصل 8). ويكون تعقيد خوارزمية كروسكال بالتالي O(E log E).

  topological_sort: (vertex -> unit) -> graph -> unit