إيجاد الحد الأدنى من شجرة الامتداد من قائمة الجوار حيث الجوار القائمة في صفيف سلسلة باستخدام خوارزمية Prims

Question

لذلك أنا بحاجة إلى بعض المساعدة في الخروج مع وسيلة لإيجاد الحد الأدنى من شجرة الامتداد.لنفترض لدي الرسم البياني في شكل قائمة الجوار:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

الرسالة الأولى يقول والعقدة التي كنت تبحث في عدد يروي كيف العديد من اتصالات إلى أي عقدة أخرى هناك.على سبيل المثال ، قد اتصالين واحد كل I. Bبعد أن الرقم الذي يلي الحروف ببساطة قل وزن الحافة.B الوزن 12 وأنا الوزن 25.إذا كنت قد خططت أصلا لتمثيل هذه الأمور كلها كما صفيف سلسلة دعا Graph[8].كل سطر ستكون مختلفة فتحة في الصفيف.أواجه صعوبات في معرفة كيفية تحقيق ذلك إما Prims أو Kruskalls الخوارزمية.

Answer 1

لنفترض لدي شجرة في شكل قائمة الجوار

المهم (على تفهمكم) ملاحظة أن لديك اتصال الرسم البياني في هذا النوع من الجوار القائمة ، ولكن أعتقد أنه كان مجرد خطأ مطبعي.وسوف أقترح هذا تحرير, ولكن أنا فقط أريد منك أن تكون على علم به.حقيقة أنه هو الرسم البياني و لا شجرة يمكن أن ينظر إليه من هذه الخطوط:

A 2 B 12 I 25
B 3 C 10 H 40 I 8

هنا لديك دائرة بالفعل في A-B-I:

     A
  12/_\25
   B 8 I

وجود دائرة التعريف يعني أنه لا يمكن أن تكون شجرة!هناك أكثر من شيء واحد يمكن أن نرى من الطريقة التي قدمت هذا بياني ثانوي:حواف الأوزان ، وليس العقد.

---

الآن دعونا نلقي نظرة على المقدمة سبيل المثال:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

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

E 2 F 60 G 38
F 0

السطر الأول هنا يظهر ميزة من E إلى F, بعد السطر الثاني يقول و كان على درجة من 0 ، ولكن درجة يحددها حواف الحادث إلى ذلك!

هذا ما قائمة الجوار تبدو كما لو كانت "كاملة":

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

يمكننا أن نرى الكثير من التكرار لأن كل حافة يحدث مرتين, هذا هو السبب الخاص بك 'الأمثل' الجوار قائمة أفضل يناسب احتياجاتك - سيكون هذا 'كاملة' على سبيل المثال أن العديد من عديمة الفائدة الشيكات.ومع ذلك ، يجب أن فقط الاعتماد على هذا إذا كان يمكنك أن تكون متأكدا من أن جميع البيانات الواردة إلى التعليمات البرمجية الخاصة بك هو بالفعل 'الأمثل' (أو بالأحرى في هذا الشكل)!أنا سأعتبر هذه معين من الآن فصاعدا.

---

دعونا نتحدث عن بنية البيانات الخاصة بك.يمكنك بالطبع استخدام المقترح مجموعة من السلاسل ، ولكن أن نكون صادقين ، وأود أن لا يوصي بشيء مثل @AmirAfghani المقترحة بنية البيانات.باستخدام هذا النهج من شأنه أن يجعل عملك أسهل (لأنه - كما سبق أن ذكرنا - أن يكون أقرب إلى التمثيل العقلي) وحتى أكثر كفاءة (أعتقد لا تعتمد على هذا تخمين ;)) كما كنت تفعل العديد من العمليات على سلاسل خلاف ذلك.في العنوان طلبت بعد زم خوارزمية لكن في السؤال الفعلي قلت إما متزمت أو Kruskal هو.سوف أذهب مع Kruskal ببساطة لأن الخوارزمية هي الطريقة الأسهل و يبدو أنك تقبل على حد سواء.

---

Kruskal خوارزمية

Kruskal خوارزمية بسيطة إلى حد ما ، إنها في الأساس:

• تبدأ مع كل عقدة ، ولكن عدم وجود حواف

كرر التالية قدر المستطاع:

• من غير مستخدمة/unchosen حواف اختيار واحد مع أقل وزن (إذا كان هناك أكثر من واحد:مجرد اختيار واحد منهم)
• تحقق مما إذا كان هذا الحافة سوف يسبب دائرة, إذا فعلت ذلك, وضع علامة على أنها اختيار 'تجاهل' عليه.
• إذا كان لا يسبب دائرة استخدامه وعلامة على أنها تستخدم/المختار.

هذا كل شيء.انها حقا بهذه البساطة.ومع ذلك أود أن أذكر شيئا واحدا في هذه المرحلة ، وأعتقد أنه يناسب هنا:لا يوجد "الدنيا شجرة الامتداد" ، ولكن "الحد الأدنى شجرة الامتداد" كما يمكن أن يكون هناك العديد من ، لذلك قد تختلف النتائج الخاصة بك!

---

العودة إلى بنية البيانات الخاصة بك!قد نرى الآن لماذا سيكون فكرة سيئة لاستخدام مجموعة من السلاسل بوصفها بنية البيانات.يمكنك تكرار العديد من العمليات على سلاسل (على سبيل المثال التحقق من وزن كل حافة) ، سلاسل ثابتة, هذا يعني أنه لا يمكنك ببساطة 'رمي' واحدة من الحواف أو علامة واحدة من حواف بأي طريقة.باستخدام نهج مختلف يمكنك فقط تعيين الوزن إلى -1 ، أو حتى إزالة الإدخال على الحافة!

---

البحث المتعمق الأول

من ما شاهدته أعتقد أن المشكلة الرئيسية هي تحديد ما إذا كانت ميزة من شأنها أن تسبب دائرة أو لا, صحيح ؟ أن تقرر هذا, سيكون لديك على الأرجح دعوة عمق-أول خوارزمية البحث و استخدام قيمة الإرجاع.الفكرة الأساسية هي هذه:بداية من العقد (سأتصل هذه العقدة الجذر) و في محاولة لايجاد وسيلة إلى عقدة في الطرف الآخر من المختار حافة (سأتصل هذه العقدة الهدف عقدة).(طبعا في الرسم البياني الذي لا يملك هذه الحافة حتى الآن)

• اختيار واحد لم تسبق زيارتها حافة الحادث إلى الجذر الخاص بك
• بمناسبة هذا المختار الحافة كما زار (أو شيء من هذا القبيل, كل ما تريد)
• كرر الماضيين خطوات العقدة على الجانب الآخر من زار الحافة
• كلما كان هناك لم تسبق زيارتها حواف العودة من حافة واحدة
• إذا كنت تعود في الجذر الخاص بك لا لم تسبق زيارتها حواف الحادث إلى ذلك المتبقية ، كنت فعلت.return false.
• إذا كنت في أي وقت الزيارة الهدف الخاص بك عقدة الانتهاء.العودة الحقيقية.

الآن, إذا كان هذا الأسلوب بإرجاع true هذه الحافة من شأنه أن يسبب دائرة.

Answer 2

ليست الإجابة المباشرة على سؤالك لكل مقول (يبدو أنك تقوم بأداء المدرسة)، لكنني أعتقد أنه سيساعدك البدء في البدء.لماذا لا تنشئ بنية بيانات تطابق عن كثب نموذج العقلي وبناء من هناك؟ giveacodicetagpre.