0

我正在尝试在 C++ 中实现 Kruskal 算法。我按照 youtube 视频中的说明进行操作，其中使用了矢量。尽管代码在视频中显示准确运行，但相同的代码甚至无法在我的 PC 中编译。我无法弄清楚问题所在。这是代码：#include #include using namespace std;

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;
}
4

1 回答 1

0

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

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

还有几个错误：

  1. 该函数的名称是MakeSet()，并且您正在使用它来调用它Makeset()
  2. 您在循环中使用roo2了而不是root2for(Edge e: g.edges){}
  3. 循环中的cout语句在for(Edge e: A){}语法上不正确。
于 2015-04-11T18:02:30.767 回答