-1

I am trying to create a maximum spanning tree in C++ but am having trouble preventing cycles. The code I have works alright for some cases, but for the majority of cases there is a cycle. I am using an adjacency matrix to find the edges.

double maximumST( vector< vector<double> > adjacencyMatrix ) {

    const int size = adjacencyMatrix.size();
    vector <double> edges;
    int edgeCount = 0;
    double value = 0;
    std::vector<std::vector<int>> matrix(size, std::vector<int>(size));

    for (int i = 0; i < size; i++) {
        for (int j = i; j < size; j++) {
            if (adjacencyMatrix[i][j] != 0) {
                edges.push_back(adjacencyMatrix[i][j]);
                matrix[i][j] = adjacencyMatrix[i][j];
                edgeCount++;
           }
       }
    }

    sort(edges.begin(), edges.end(), std::greater<int>());

    for (int i = 0; i < (size - 1); i++) {
        value += edges[i];
    }

    return value;

}

One I've tried to find a cycle was by creating a new adjacency matrix for the edges and checking that before adding a new edge, but that did not perform as expected. I also tried to build a 3D matrix, but I could not get that to work either.

What's a new approach I should try to prevent cycles?

Tanner
  • 477
  • 7
  • 21
  • 1
    Sorry, can't quite see your approach: how was this supposed to work? At the moment you're simply pushing every edge found in the adjacency matrix. You'd need to somehow remember which vertices you already reached and there's nothing in your code to do that. – BeyelerStudios Oct 24 '16 at 15:52

1 Answers1

0

You should add the edge if the lowest common ancestor(LCA) of the two vertices corresponding to that edge is not root.

CPP_NEW
  • 197
  • 2
  • 9