[Urgent] Minimum spanning tree

[nightmaregiba]

Here is my code

//input:
4
0 -3 5 2
-3 0 1 0
5 1 0 1
2 0 1 0

#include<iostream>
#include<fstream>
#define fin "d:\\input.txt"
#define fon "d:\\output.txt"
using namespace std;
ifstream fi;
ofstream fo;

void OpenFileRead(){
    fi.open(fin,ios::in);
    if(!fi){
        cout<<"File Not Found\n";
        system("pause");
        exit(1);
    }
}

void OpenFileWrite(){
    fo.open(fon,ios::out);
    if(!fo){
        cout<<"File Not Found\n";
        system("pause");
        exit(1);
    }
}

void ReadData(int G[][100], int &n){
    OpenFileRead();
    fi>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) fi>>G[i][j];
    fi.close();
}

int Prim(int G[][100], int n, int P[], int MAX){
 int *Not = new int[n+1];
 int  u=1;
 int  *d = new int [n+1];
 for(int i=1; i<=n; i++){
 Not[i] = 1;
 d[i] = MAX;
 }
 Not[1] = 0;
 for(int i=1; i<=n-1; i++){
 for(int v=2; v<=n; v++){
 if(Not[v] && d[v] > G[u][v]){
 d[v] = G[u][v];
 P[v] = u;
 }
 }
 u = 0;
 int dmin = MAX;
 for(int v=2; v<=n; v++){
 if(Not[v] && d[v]<dmin){
 dmin = d[v];
 u = v;
 }
 }
 if(u==0) return 0;
 Not[u] = 0;
 }
 return 1;
}
/******************************* Write Result *********************************/
void WriteResult(int G[][100], int n, int P[]){
 int B=0;
 for(int i=2; i<=n; i++){
 fo<<min(P[i],i)<<" - ";
 fo<<max(P[i],i)<<endl;
 B += G[i][P[i]];
 }
 fo<<B<<endl;
}
/********************************** Main **************************************/
int main(){
 int G[100][100], n, P[100];
 ReadData(G, n);
 OpenFileWrite();
 if(Prim(G, n, P, 35000)) WriteResult(G, n, P);
 else fo<<"Not Built";
 fo.close();
}

 

the result should be:
1-2
2-3
3-4
-1

but it is
1 - 2
2 - 3
2 - 4
-2


Help me! Thhks a bunch!!1

[Duthomhas]

Draw the graph. There is no edge 2-4. Your solution is correct.

[edit] Oops. I read that backwards. I'll have to look at your code to see why it is reporting an edge that doesn't exist.

[nightmaregiba]

There is no edge 2-4. But i cant find out what is wrong in code

[ne555]

¿so we can have negative weights but not zero?

You are reporting a non-existent edge because you never check for existence
/*46*/ if(Not[v] && d[v] > G[u][v])

[nightmaregiba]

yes, we can have negative

[nightmaregiba]

Someone else have the code????

[Smac89]

When you post code, you should identify where the problem is - what is working and what isn't - and then ask for help regarding that specific problem. Posting code and saying "Output is supposed to be A but it is B" doesn't help me as much as it has helped you to understand where the problem is. This is especially true when the output has nothing to do with syntax but everything to do with your logic.
And then to add salt your have basically requested for someone to write the code for you. tsk tsk.

I am just going with keywords here to identify what you need help with. So you are trying to implement a minimum spanning tree algorithm - Prim's algorithm to be exact. Well a quick search on google has revealed pseudocode for this algorithm: http://en.wikipedia.org/wiki/Prim's_algorithm

Also note that the area in the pseudocode that says `u = Extract-Min(Q)` requires the use of a heap data structure if you want the algorithm to be reasonably fast for large input.

[nightmaregiba]

logic is right but result isn't, i cant identify the problem so i have to post all the code... It easier for you to check from the beginning to the end! right?

If i know where the problem, it will post the problem only. why i have to post the long long code like that???? i have thought before i post it---

[Duthomhas]

@Smac89
OP has done nothing wrong. He has posted his (short!) code, explained exactly what the problem is (reporting invalid edge), and asked for help regarding that specific problem.

Programming comes in two parts. If all user problems were just a matter of syntax we members of the forum would be obviated. The problem is his logic, which is exactly where he is having a problem, and what he has asked us to help with.

And he never asked anyone to write code for him.

Also, you are sidestepping his problem by looking up Wikipedia instead of understanding his algorithm. Just because it is "Prim's" doesn't mean there aren't multiple ways to handle it. Part of the point of Prim's is that you don't need any particularly fancy data structures to handle it. Adding a heap to the mix increases complexity unnecessarily.

@nightmaregiba
Sorry, I haven't had time to look at your code until now, but ne555 has already identified the errors for you.

Error 1:
The graph, the way it is described (in the adjacency matrix), means that it is possible to have an edge of any weight except zero. This is why ne555 specifically asked you about it.

Frankly, I don't think there's much you can do about it, since it is part of your assignment, alas. Just continue to assume that an edge of weight zero is the same as saying 'no edge'.

Error 2:
On line 46 you have forgotten the last issue -- an edge of weight zero means 'no edge'. In addition to your existing condition, you must also make sure that the edge (u,v) is not zero. (Because if it is, there really isn't an edge there.)

Fix that, and you'll see the correct output.

ne555 is sometimes difficult to understand because he doesn't waste many words, but he is very intelligent and often asks questions that are designed to lead you to find the answer for yourself.

Hope this helps.

[nightmaregiba]

Hi Duoas

I appreciate what you wrote. Finally i have found the error.

Thank you so much!!!!