مساء الخير
حابه اسئلكم عن مشروعي انا مبتديئه في البرمجه
وهذا مشروعي
طبعاً انا حليته بس مو عارفه اذا فهمت الفكره صح أو لا.؟
وكمان عندي مشكله بالأكواد فيها اخطااء ماعرفت اصححها
اتمنى تفيدووني
وشكراً
Minimum Spanning Tree
Description
Given graph G which is a connected, weighted, undirected graph, a spanning tree T is a subgraph
of G which is: (1) a tree that (2) connects all the vertices of G together. The weight of a spanning
tree is the sum of the weights of the edges in that tree. A minimum spanning tree is a spanning
tree: (3) whose weight is less than or equal to the weight of every other spanning tree.
Write a program that determines if a given tree T is a Minimum Spanning Tree for a given graph G.
Input Format
Your program will be tested on one or more test cases. For each test case you’ll be given a graph
G and one or more trees to test. The first line of a test case will have a single positive integer n
denoting the number of vertices in G (where 1 < n ≤ 1000). The vertices are numbered starting
from 1. The next (n−1) lines specify the upper triangle of the graph’s adjacency matrix as seen
here:
W1,2 W1,3 . . . W1,n−1 W1,n
W2,3 W2,4 . . . W2,n
...
Wn−1,n
where Wi,j is the weight of the edge between vertices i and j. Wi,j = 0 iff there is no edge between
i and j. Note that 0 ≤ Wi,j ≤ 1000
Following the graph specification, a test case will specify a single positive number Q on a separate
line where 0 < Q ≤ 1000. Q denotes the number of trees to test on the given graph.
Each tree either consists of a single vertex, given by its number, or is specified as:
( R T1 T2 . . . Tc )
where R is the number of the vertex at the root and T1,. . . ,Tc (where 0 < c ≤ 1000) are the
sub-trees of R specified recursively.
The last line of the input file will have a single zero.
Output Format
For each query, write the result on a separate line using the following format:
a.b._result
where a is the test case number (starting at 1,) and b is the query number within this test case
(again starting at 1.) result is either "YES" or "NO" indicating if the tree is a minimum spanning
tree or not.
The following figures illustrate the sample I/O. The top half is for the first test case, while the
second test case is on the bottom. In the graph, vertex numbers are underlined and the edges of a minimum spanning tree are drawn in thicker lines.
ــــــــــــــــــــــــــــــــــــــــــــــــــ
#include <iostream>
#include <conio.h>
#define ROW 7
#define COL 7
#define infi 5000 //infi for infinityclass prims
{
int graph[ROW][COL],nodes;
public:
prims();
void createGraph();
void primsAlgo();
};
prims :: prims(){
for(int i=0;i<ROW;i++)
for(int j=0;j<COL;j++)
graph[j]=0;
}
void prims :: 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;
}
}
}
void prims :: 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();
}
