يعني مخطط السلطة المزعوم أن كل حافة في المخطط سيكون لها مجموعة أو مجموعة من القيم المقابلة. عادة ، هذه القيمة مجرد رقم
على سبيل المثال: في شبكة النقل ، قد يمثل الوزن على الجانب المسافة أو تكلفة النقل (من الواضح أن كلاهما أرقام). ومع ذلك ، قد يكون الوزن على الحافة أيضًا شيئًا آخر ، مثل سلسلة أو حتى حزمة بيانات أكثر تعقيدًا ، تجمع المزيد من البيانات
الفكرة الأساسية لخوارزمية Kruskar هي: في الرسم البياني للاتصال المرجح ، يتم العثور على أصغر حافة باستمرار في مجموعة الحافة. إذا كانت الحافة تلبي شروط الحصول على الحد الأدنى لشجرة الامتداد ، فسيتم بنائها حتى يتم الحصول على شجرة تمتد على الأقل.
خطوات التنفيذ لخوارزمية كروسكار:
الخطوة 1: في الرسم البياني للاتصال المرجح ، فرز أوزان الحواف ؛
الخطوة 2: حدد ما إذا كنت بحاجة إلى تحديد هذه الحافة (في هذا الوقت ، تم فرز الحواف في الشكل من وزن صغير إلى كبير). أساس الحكم هو ما إذا كانت رؤوس الحافة متصلة. إذا كانت متصلة ، تابع إلى المرحلة التالية ؛ إذا لم تكن متصلة ، فاختر توصيلها.
الخطوة 3: حلقة الخطوة الثانية حتى تكون جميع القمم في الرسم البياني في نفس المكون المتصل ، مما يعني الحصول على الحد الأدنى لشجرة الامتداد.
فيما يتعلق بتنفيذ الرسم البياني للإذن ، راجع المثال التالي:
الرسم البياني:
حزمة kruskal ؛ الرسم البياني للفئة العامة {Final int max = 100 ؛/** vertex node*/public class vexnode {int adjvex ؛ int data ؛} vexnode [] vexnodes ؛ int [] thevexs ؛ // vertex set int [] a ، int [] vexs) {thevexs = vexs ؛ for (int i = 0 ؛ i <vexs.length ؛ i ++) {for (int j = 0 ؛ j <vexs.length ؛ j ++) {graph.edges [i] [j] = a [i] ؛ graph.thevexs.length ؛ {system.out.printf ("٪ 4D" ، graph.edges [i] [j]) ؛}} system.out.println ("/n") ؛}}}الخوارزمية:
حزمة kruskal ؛ الفئة العامة kruskal {public class edge {int start ؛ int end ؛ int inter ؛} public void sortedge (edge [] e ، int e) {edge temp ؛ int j ؛ for (int i = 0 ؛ i <e ؛ i ++) {temp = e [i [i] ؛ e [j] ؛ j-؛} e [j+1] = temp ؛}} kruskal (الرسم البياني الرسم البياني) {int i ، j ، u1 ، v1 ، sn1 ، sn2 ، k ؛ int [] vset = new int [100] (j = 0 ؛ j <= i ؛ j ++) {e [k] = new edge () ؛ if (graph.edges [i] [j]> 0) {e [k] .start = i ؛ e [k] .end = j ؛ e [k] (i = 0 ؛ i <graph.thevexs.length ؛ i ++) {vset [i] = i ؛} k = 1 ؛ j = 0 ؛ بينما (k <graph.thevexs.length) {u1 = e [j]. {system.out.printf ("(٪ d ، ٪ d) ، الوزن: ٪ d" ، u1 ، v1 ، e [j]. {vset [i] = sn1 ؛}}} j ++ ؛}}}فئة الاختبار:
حزمة kruskal ؛ اختبار الفئة العامة {public static void main (string [] args) {int [] vexs = {0،1،2،3،4} ؛ int [] [] a = {{0،1،3،4،7} ، {1،0،2 ، -1 ، -1} ، {3،2،0،5،8} ، {4 ، -1،5،0،6} ، {7 ، -1،8،6،0} ؛ Kruskal = New Kruskal (Graph) ؛}}لخص
ما ورد أعلاه هو المحتوى الكامل لهذه المقالة حول مثال رمز لغة Java لتنفيذ خوارزمية Cruzkal بناءً على الرسوم البيانية غير المصرح بها. آمل أن يكون ذلك مفيدًا للجميع. إذا كان لديك أي أسئلة ، فيرجى ترك رسالة في أي وقت. سيبذل المحرر قصارى جهده للإجابة عليك.