Start New Discussion within our Software Development Community

Hello, I know that you don't provide solutions to homework but I know Daniweb will help with homework as long as we show we are doing some work ourselfs. My assignment is to generate the maximum spanning tree for a given matrix. I am CLOSE but not quite there. I am not really following line for line any algorithm as most were too confusing for me to implement. I have this code which I wrote:

double maximumST( vector< vector<double> > adjacencyMatrix ){
    int rcSize = adjacencyMatrix[0].size();
    double curMax = 0;
    double returnmax = 0;
    bool visited[rcSize];

    for( int k = 0; k < rcSize; k++ ){
        for( int i = 0; i < rcSize; i++ ){
            for( int j = 0; j < (rcSize - i); j++){
              if(adjacencyMatrix[i][j] > curMax && (visited[i] == false || visited[j] == false)){
                curMax = adjacencyMatrix[i][j];
                visited[i] = true;
                visited[j] = true;
                //cout << i << " " << j << endl;
              }
            }
            returnmax = returnmax + curMax;
            curMax = 0;
        }
    }
  return returnmax;
}

which "works" but the only problem it does have is that for most tables it will leave off an edge. I know why but I am not sure how to address it without breaking more things. My if statement checks to see if all the values have been visited which is tracked VIA the bool array (visited). The reason I am keeping track of that is so that I don't run into a cycle, but the problem then comes that for something like the following:

0 7 5 9 9
7 0 9 2 9
5 9 0 9 2
9 2 9 0 9
9 9 2 9 0

I get 27 where the answer is 36, the reason is that the 9 connection 3 -> 2 is not connected because everything is connected already so that if statement won't allow it to add that edge... The edges that it finds are:
0 -> 3
0 -> 4
1 -> 2
but it needs
3 -> 2

Any ideas how I can restructure that logic?

You aren't providing enough information. You need to show what is in your adjacencyMatrix first of all, and then you need to provide additional code in your application.

This article has been dead for over six months. Start a new discussion instead.