Implementación del algoritmo kruskal en ejemplo de código c ++

Luego de mucho batallar hemos dado con la solución de este conflicto que tantos lectores de este sitio web han presentado. Si quieres aportar alguna información no dudes en dejar tu conocimiento.

Ejemplo: Kruskals en c ++

#includeusingnamespace std;typedef  pair<int,int> iPair;structGraphint V, E; 
    vector< pair<int, iPair>> edges;Graph(int V,int E)this->V = V;this->E = E;voidaddEdge(int u,int v,int w) 
        edges.push_back(w,u, v);intkruskalMST();;structDisjointSetsint*parent,*rnk;int n;DisjointSets(int n)this->n = n; 
        parent =newint[n+1]; 
        rnk =newint[n+1];for(int i =0; i <= n; i++) 
            rnk[i]=0; 
  
      
            parent[i]= i;intfind(int u)if(u != parent[u]) 
            parent[u]=find(parent[u]);return parent[u];voidmerge(int x,int y) 
        x =find(x), y =find(y);if(rnk[x]> rnk[y]) 
            parent[y]= x;else 
            parent[x]= y;if(rnk[x]== rnk[y]) 
            rnk[y]++;;intGraph::kruskalMST()int mst_wt =0;sort(edges.begin(), edges.end()); 
  

    DisjointSets ds(V); 
  

    vector< pair<int, iPair>>::iterator it;for(it=edges.begin(); it!=edges.end(); it++)int u = it->second.first;int v = it->second.second;int set_u = ds.find(u);int set_v = ds.find(v);if(set_u != set_v) 
          
            cout << u <<" - "<< v << endl; 
  
      
            mst_wt += it->first; 
  
        
            ds.merge(set_u, set_v);return mst_wt;intmain()int V =9, E =14; 
    Graph g(V, E); 
  
   
    g.addEdge(0,1,4); 
    g.addEdge(0,7,8); 
    g.addEdge(1,2,8); 
    g.addEdge(1,7,11); 
    g.addEdge(2,3,7); 
    g.addEdge(2,8,2); 
    g.addEdge(2,5,4); 
    g.addEdge(3,4,9); 
    g.addEdge(3,5,14); 
    g.addEdge(4,5,10); 
    g.addEdge(5,6,2); 
    g.addEdge(6,7,1); 
    g.addEdge(6,8,6); 
    g.addEdge(7,8,7); 
  
    cout <<"Edges of MST are n";int mst_wt = g.kruskalMST(); 
  
    cout <<"nWeight of MST is "<< mst_wt;return0;

Sección de Reseñas y Valoraciones

Eres capaz de ayudar nuestra faena exponiendo un comentario y dejando una puntuación te estamos eternamente agradecidos.

---

---

Utiliza Nuestro Buscador