東西要改變

Question

作爲標題，我不知道如何將這個結構轉換成類？ 另外我還有一個問題，我如何將數組Sets [] []和頂部[]轉換爲矢量？ 我試過了，但是在編輯[i]位置的矢量時遇到問題。

//******************************* 
// Class Kruskal    * 
//******************************* 
class kruskal 
{ 
private: 
    struct Edge { 
     //Arco: vertice V -> vertice U : peso W 
     int v, u, w; 
     Edge(int v, int u, int w) : v(v), u(u), w(w) {} 
     bool operator < (const Edge& c) const{ 
      if (w != c.w) 
       return w < c.w; 
      if (v != c.v) 
       return v < c.v; 
      return u < c.u; 
     } 
    }; 
    int n; //n. nodes 
    int nre; //n. edges 
    vector<Edge> edges; //vector contenente tutti gli archiì 
    vector<Edge> tree; //Albero che conterrà tutti gli archi dell'MST 

    int sets[100][10]; //matrice contente i sets (tagli) 
    int top[100]; //supporto alla matrice dei sets 
public: 
    kruskal(){}; 
    ~kruskal(){ cout << "Grafo distrutto"; }; 
    void read_graph(); 
    void sort_edges(); 
    void algorithm(); 
    int find_node(int); 
    void print_min_span_t(); 
}; 

//******************************************* 
// read_graph()       * 
// Legge in input n, nre, e i vari archi * 
//******************************************* 
void kruskal::read_graph() 
{ 
    cout << "Algoritmo di Kruskal" << endl; 
    cout << "Minimum Spanning Tree su Grafo non orientato e pesato" << endl << endl; 
    cout << "-Inserire numero di nodi e numero di archi: "; 
    cin >> n >> nre; 
    int v, u, w; 
    cout << "-Inserire vertice 1, vertice 2 e peso:" << endl; 
    for (int i = 0; i < nre; i++) 
    { 
     cin >> v >> u >> w; 
     if (w != 0) 
     { 
      edges.push_back(Edge(v, u, w)); 
     } 
    } 
    //Print graph edges 
    cout << endl << endl << "Archi del grafo:" << endl; 
    for (unsigned int i = 0; i < edges.size(); i++) 
    { 
     cout << " < " << edges[i].v 
      << " , " << edges[i].u 
      << " > " << edges[i].w << endl; 

    } 
} 

//******************************************* 
// sort_edges()       * 
// Ordina gli archi per peso con sort() * 
//******************************************* 
void kruskal::sort_edges() 
{ 
    sort(edges.begin(), edges.end()); 
    //Print graph edges 
    cout << endl << endl << "Archi del grafo dopo l'ordinamento:" << endl; 
    for (unsigned int i = 0; i < edges.size(); i++) 
    { 
     cout << " < " << edges[i].v 
      << " , " << edges[i].u 
      << " > " << edges[i].w << endl; 
    } 
} 

//*********************************************** 
// algorithm()         * 
// Inizializza i sets (make-set)    * 
// Trova i sets dei due nodi (Find_node)  * 
// Controlla se i sets sono diversi (Findset) * 
// Se si lo inserisce nel vector "tree" (MST) * 
// E unisce i due sets (Union)     * 
// Altrimenti "scarta" l'arco     * 
//*********************************************** 
void kruskal::algorithm() 
{ 
    //Make-set 
    for (int i = 1; i <= n; i++) 
    { 
     sets[i][1] = i; 
     top[i] = 1; 
    } 
    cout << endl << "Avvio algoritmo di Kruskal:" << endl << endl; 
    for (unsigned int i = 0; i < edges.size(); i++) 
    { 
     int p1 = find_node(edges[i].v); 
     int p2 = find_node(edges[i].u); 
     //Findset(p1) != Findset(p2) 
     if (p1 != p2) 
     { 
      cout << "Arco preso nell'albero:" 
       << " < " << edges[i].v << " , " 
       << edges[i].u << " > " << endl << endl; 
      //Union 
      tree.push_back(Edge(edges[i].v, edges[i].u, edges[i].w)); 

      //Union two sets 
      for (int j = 1; j <= top[p2]; j++) 
      { 
       top[p1]++; 
       sets[p1][top[p1]] = sets[p2][j]; 
      } 
      top[p2] = 0; 
     } 
     else 
     { 
      cout << "Questo arco" 
       << " < " << edges[i].v << " , " 
       << edges[i].u << " > " << "forma un ciclo ed e' stato rimosso" << endl << endl; 
     } 
    } 
} 

//******************************************* 
// find_node()        * 
// Trova il sets di appartenenza del nodo * 
//******************************************* 
int kruskal::find_node(int n) 
{ 
    for (int i = 1; i <= nre; i++) 
    { 
     for (int j = 1; j <= top[i]; j++) 
     { 
      if (n == sets[i][j]) 
       return i; 
     } 
    } 

    return -1; 
} 

//******************************* 
// print_min_span_t()   * 
//******************************* 
void kruskal::print_min_span_t() 
{ 
    cout << endl << "Minimum Spanning Tree del grafo:" << endl; 
    for (unsigned int i = 0; i < tree.size(); i++) 
    { 
     cout << " < " << tree[i].v 
      << " , " << tree[i].u 
      << " > " << tree[i].w << endl; 
    } 
} 

Answer 1

由於top是對應sets的只是大小，您可以刪除top，並改變std::vector<std::vector<int> > sets。

然後

MakeSet：

//Make-set 
sets.resize(nre); // or n, not sure of the definition of each one... 
for (std::size_t i = 0; i != nre; ++i) 
{ 
    sets[i].push_back(i); 
} 

UnionSet：

//Union two sets 
sets[p1].insert(sets[p1].end(), sets[p2].begin(), sets[p2].end()); 
sets[p2].clear(); 

查找節點：

int kruskal::find_node(int n) const 
{ 
    for (size_t i = 0; i != sets.size(); ++i) 
    { 
     if (std::find(sets[i].begin(), sets[i].end(), n) != sets[i].end()) 
     { 
      return i; 
     } 
    } 
    return -1; 
}