使用 STL 在 C++ 中实现 Kruskal 算法

Question

我正在尝试用 C++ 实现 Kruskal 算法。我按照使用矢量的 youtube 视频中的说明进行操作。尽管代码在视频中显示运行准确，但相同的代码甚至无法在我的 PC 中编译。我无法弄清楚问题所在。这是代码：＃包括＃包括使用命名空间标准；

struct Edge{
char vertex1;
char vertex2;
int weight;
Edge(char v1, char v2, int w):vertex1(v1),vertex2(v2),weight(w){}
};

struct Graph
{
vector<char> vertices;
vector<Edge> edges;
};

unordered_map<char,char> PARENT;
unordered_map<char, int> RANK;

char Find(char vertex){
if(PARENT[vertex]==vertex)
    return PARENT[vertex];
else
    return Find(PARENT[vertex]);
}

void Union(char root1, char root2)
{
if(RANK[root1]>RANK[root2]){
    PARENT[root2]=root1;
}
else if(RANK[root2]>RANK[root1]){
    PARENT[root1]=root2;
}
else{
    PARENT[root1]=root2;
    RANK[root2]++;
}
}

void MakeSet(char vertex){
PARENT[vertex] = vertex;
RANK[vertex] = 0;
}

void Kruskal(Graph& g)
{
vector<Edge> A;
for(auto c: g.vertices){
    Makeset(c);
}
sort(g.edges.begin(),g.edges.end(), [](Edge x, Edge y)
{return x.weight<y.weight;});

for(Edge e: g.edges){
    char root1 = Find(e.vertex1);
    char root2 = Find(e.vertex2);
    if(root1!=root2){
        A.push_back(e);
        Union(root1, roo2);
    }
}

for(Edge e: A){
    cout << e.vertex1 << "----" << e.vertex2 << " " e.weight << endl;
}
}

int main()
{
char t[]={'a','b','c','d','e','f'};

Graph g;
g.vertices = vector<char>(t,t+sizeof(t)/sizeof(t[0]));

char sv,ev;
int wt;
while(!EOF){
    cin >> sv >> ev >> wt;
    g.edges.push_back(Edge(sv,ev,wt));
}

Kruskal(g);

return 0;
}

Answer 1

您需要在代码中包含一些头文件：

unordered_map 使用 unordered_map STL。此外，您只能在 C++11 和 C++14 中使用它。
vector 使用矢量 STL。
algorithm 使用内置的 sort() 函数。

还有一些错误：

函数的名称是 MakeSet()，您正在使用 Makeset()
您在 for(Edge e: g.edges){} 循环中使用 roo2 而不是 root2
for(Edge e: A){} 循环中的 cout 语句语法不正确。

使用 STL 在 C++ 中实现 Kruskal 算法

Kruskal algorithm implementation in C++ using STL

stl

vector

kruskals-algorithm