السلام عليكم ورحمة الله وبركااته
ياجماعه انا مبتديئه في البرمجه و عندي مشرووع عن ال minimum spanning tree وماعندي ادنى فكره عنها
بحثت كثير وحاولت افهم ومبدئياً كتبت الأكواد
لكن مااعرف اذا انا فهمت الفكره صح أو لا
وكمان الأكواد ماتشتغل عندي فيها اخطاء مو عارفه اصححها
اتمنى مساعدتكم
الترجمه من قوقل
الحد الأدنى شجرة الامتداد
وصف
نظرا G الرسم البياني الذي هو مرجح، متصلة، الرسم البياني غير موجهة، وتي شجرة تمتد هو subgraph
من G التي هي: (1) شجرة (2) يربط جميع القمم من G معا. ثقل الممتدة
شجرة هو مجموع أوزان حواف في تلك الشجرة. الشجرة التي تغطي الحد الأدنى هي التي تغطي
شجرة: (3) الذين يكون وزنهم أقل من أو مساو لوزن كل شجرة أخرى تمتد.
كتابة برنامج الذي يحدد ما إذا كان T شجرة معينة هي شجرة الامتداد الحد الأدنى للحصول على الرسم البياني نظرا G.
نسق إدخال
وسيتم اختبار البرنامج على حالات الاختبار واحد أو أكثر. سيكون لكل حالة اختبار أن تحصل على رسم بياني
G واحد أو أكثر من الأشجار لاختبار. والسطر الأول من حالة اختبار لديها واحدة ايجابية عدد صحيح ن
تدل على عدد من القمم في G (حيث 1 <ن ≤ 1000). يتم ترقيم القمم انطلاق
من 1. التالي (N-1) تحديد خطوط مثلث العلوي من مصفوفة الجوار على الرسم البياني كما ترى
هنا:
W1، 2 W1، 3. . . W1، N-1 W1، ن
W2، 3 W2، 4. . . W2، ن
...
WN-1، ن
حيث واي، ي هو وزن الحافة بين القمم وأنا ي. واي، ي = 0 المنتدى ليس هناك حافة بين
i و j. لاحظ أن 0 ≤ واي، ي ≤ 1000
بعد تحديد الرسم البياني، وحالة اختبار تحديد عدد واحد س إيجابي على منفصلة
خط حيث 0 <س ≤ 1000. سؤال يدل على عدد من الأشجار لاختبار على الرسم البياني معين.
كل شجرة ويتكون إما من قمة واحدة، نظرا لعدد منها، أو تم تعيينه على النحو التالي:
(R T1 T2 ... TC)
حيث R هو رقم من قمة الرأس في جذر وT1،. . . ، والتعاون التقني (حيث 0 <ج ≤ 1000) هي
شبه أشجار R المحدد بشكل متكرر.
والسطر الأخير من ملف الإدخال لديها صفر واحد.
تنسيق الإخراج
كل استعلام، وكتابة النتيجة على سطر منفصل باستخدام الشكل التالي:
a.b._result
حيث هو رقم حالة اختبار (بدءا من 1،) و (ب) هو رقم الاستعلام في هذه الحالة اختبار
(بدءا من جديد في 1). النتيجة هي إما "نعم" أو "لا" مشيرا الى شجرة وإذا هو الحد الأدنى الذي يمتد
شجرة أم لا
صوره للمشروع بالمدخلات والمخرجات
محاولتي في الحل
#include <iostream>
using name space std;
#define ROW 7
#define COL 7
#define infi1000 //infi for infinityclass prims
{
int graph[ROW][COL],nodes;
public:
prims();
void createGraph();
void primsAlgo();
};
{
for(int i=0;i<ROW;i++)
for(int j=0;j<COL;j++)
graph[j]=0;
}
createGraph(){
int i,j;
cout<<"Enter Total Nodes : ";
cin>>nodes;
cout<<"\n\nEnter Adjacency Matrix : \n";
for(i=0;i<nodes;i++)
for(j=0;j<nodes;j++)
cin>>graph[j];
//Assign infinity to all graph[j] where weight is 0.for(i=0;i<nodes;i++){
for(j=0;j<nodes;j++){
if(graph[j]==0)
graph[j]=infi;
}
}
}
primsAlgo(){
int selected[ROW],i,j,ne; //ne for no. of edgesintfalse=0,true=1,min,x,y;
for(i=0;i<nodes;i++)
selected=false;
selected[0]=true;
ne=0;
while(ne < nodes-1){
min=infi;
for(i=0;i<nodes;i++)
{
if(selected==true){
for(j=0;j<nodes;j++){
if(selected[j]==false){
if(min > graph[j])
{
min=graph[j];
x=i;
y=j;
}
}
}
}
}
selected[y]=true;
cout<<"\n"<<x+1<<" --> "<<y+1;
ne=ne+1;
}
}
void main(){
prims MST;
clrscr();
cout<<"\nPrims Algorithm to find Minimum Spanning Tree\n";
MST.createGraph();
MST.primsAlgo();
getch();
}
