最大スパニングツリーのサイクルを防止する

Question

C++で最大スパニングツリーを作成しようとしていますが、サイクルを防ぐのに問題があります。私が使っているコードは、いくつかのケースで問題なく動作しますが、大半のケースではサイクルがあります。私はエッジを見つけるために隣接行列を使用しています。私はサイクルを見つけることを試みてきました

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; 

} 

一つは、エッジのための新たな隣接行列を作成し、新しいエッジを追加する前にそれを確認することであったが、予想通り、それは実行されませんでした。私は3Dマトリクスを構築しようとしましたが、それを動作させることができませんでした。

サイクルを防止するための新しいアプローチは何ですか？

Answer 1

エッジに対応する2つの頂点の最小共通祖先（LCA）がルートでない場合は、エッジを追加する必要があります。