Как я могу улучшить это минимальное дерево о шнурке - алгоритм Крускала в C ++ ⇐ C++

[Anonymous]

Вот реализация алгоритма Крускала в C ++. < /p>
#include
#include
#include
using namespace std;

#define edge pair

class Graph {
private:
vector G; // graph
vector T; // mst
int *parent;
int V; // number of vertices/nodes in graph

public:
Graph(int V) {
parent = new int[V];
//i 0 1 2 3 4 5
//parent 0 1 2 3 4 5

for (int i = 0; i < V; i++) {
parent = i;
}

G.clear();
T.clear();
}

void AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
< /code>
Использование 'find_set (int i)' можно получить родительские данные. Получив родитель, может обнаружить циклы (то есть, если 2 узла имеют одинакового родителя). < /P>
int find_set(int i) {
if (i == parent) {
return i; // if i is the parent of itself
}

// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
return find_set(parent);
}
< /code>
Текущие родительские данные устанавливаются 'union_set (int u, int v)'. < /p>
void union_set(int u, int v) {
parent = parent[v];
}
< /code>
Это метод < /p>
void kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end()); // increasing weight

for (i = 0; i < G.size(); i++) {
uRep = find_set(G.second.first);
vRep = find_set(G.second.second);

if (uRep != vRep) {
T.push_back(G); // add to tree
union_set(uRep, vRep);
}
}
}
< /code>
График может быть визуально выражен этим. < /p>
void print() {
cout

Подробнее здесь: https://stackoverflow.com/questions/795 ... rithm-in-c