Kruskal 算法的 C++ 实现中的分段错误
Segmentation Fault in C++ implementation of Kruskal's Algorithm
我写了这段代码,它实现了 Kruskal 的最小生成树算法,当我将它提交给在线法官时会产生分段错误。我想我已经将分段错误的原因缩小到对边缘进行排序的部分。不过,我找不到此代码失败的确切原因。
struct DisjointSet{
private:
struct Node{
int size;
int repr;
Node(int rep){
size = 1;
repr = rep;
}
};
vector<Node> nodes;
public:
int makeSet(){
nodes.push_back(Node(nodes.size()));
return nodes.size() - 1;
}
int findRepresentative(int ind){
if(nodes[nodes[ind].repr].size == -1){
nodes[ind].repr = findRepresentative(nodes[ind].repr);
}
return nodes[ind].repr;
}
void unionSets(int ind1, int ind2){
int rep1 = findRepresentative(ind1), rep2 = findRepresentative(ind2);
if(rep1 != rep2){
if(nodes[rep1].size < nodes[rep2].size){
int t = rep1;
rep1 = rep2;
rep2 = t;
}
nodes[rep1].size += nodes[rep2].size;
nodes[rep2].size = -1;
nodes[rep2].repr = rep1;
}
}
};
bool compare(const pair<pair<int, int>, int> &p1, const pair<pair<int, int>, int> &p2){
return (p1.second <= p2.second);
}
int spanningTree(int V, int E, vector<vector<int>> &graph) {
vector<pair<pair<int, int>, int>> edges;
for(int i = 0;i < V;i ++){
for(int j = 0;j < V;j ++){
if(i <= j){
if(graph[i][j] != INT_MAX){
edges.push_back(make_pair(make_pair(i, j), graph[i][j]));
}
}
}
}
sort(edges.begin(), edges.end(), compare);
DisjointSet d;
for(int i = 0;i < V;i ++){
d.makeSet();
}
int weight = 0;
for(int i = 0;i < edges.size();i ++){
int u = edges[i].first.first, v = edges[i].first.second;
if(d.findRepresentative(u) != d.findRepresentative(v)){
d.unionSets(u, v);
weight += edges[i].second;
}
}
return weight;
}
您的比较功能:
bool compare(const pair<pair<int, int>, int> &p1, const pair<pair<int, int>, int> &p2){
return (p1.second <= p2.second);
}
不提供严格弱排序,因为将 2 个元素 e1
和 e2
与相同的 .second
进行比较将 return 对于 为真 e1 < e2
和 e2 < e1
都是不允许的。在排序中使用此 compare
函数会调用未定义的行为,可能导致段错误。
您需要执行以下操作:
bool compare(const pair<pair<int, int>, int> &p1, const pair<pair<int, int>, int> &p2){
return p1.second < p2.second;
}
我写了这段代码,它实现了 Kruskal 的最小生成树算法,当我将它提交给在线法官时会产生分段错误。我想我已经将分段错误的原因缩小到对边缘进行排序的部分。不过,我找不到此代码失败的确切原因。
struct DisjointSet{
private:
struct Node{
int size;
int repr;
Node(int rep){
size = 1;
repr = rep;
}
};
vector<Node> nodes;
public:
int makeSet(){
nodes.push_back(Node(nodes.size()));
return nodes.size() - 1;
}
int findRepresentative(int ind){
if(nodes[nodes[ind].repr].size == -1){
nodes[ind].repr = findRepresentative(nodes[ind].repr);
}
return nodes[ind].repr;
}
void unionSets(int ind1, int ind2){
int rep1 = findRepresentative(ind1), rep2 = findRepresentative(ind2);
if(rep1 != rep2){
if(nodes[rep1].size < nodes[rep2].size){
int t = rep1;
rep1 = rep2;
rep2 = t;
}
nodes[rep1].size += nodes[rep2].size;
nodes[rep2].size = -1;
nodes[rep2].repr = rep1;
}
}
};
bool compare(const pair<pair<int, int>, int> &p1, const pair<pair<int, int>, int> &p2){
return (p1.second <= p2.second);
}
int spanningTree(int V, int E, vector<vector<int>> &graph) {
vector<pair<pair<int, int>, int>> edges;
for(int i = 0;i < V;i ++){
for(int j = 0;j < V;j ++){
if(i <= j){
if(graph[i][j] != INT_MAX){
edges.push_back(make_pair(make_pair(i, j), graph[i][j]));
}
}
}
}
sort(edges.begin(), edges.end(), compare);
DisjointSet d;
for(int i = 0;i < V;i ++){
d.makeSet();
}
int weight = 0;
for(int i = 0;i < edges.size();i ++){
int u = edges[i].first.first, v = edges[i].first.second;
if(d.findRepresentative(u) != d.findRepresentative(v)){
d.unionSets(u, v);
weight += edges[i].second;
}
}
return weight;
}
您的比较功能:
bool compare(const pair<pair<int, int>, int> &p1, const pair<pair<int, int>, int> &p2){
return (p1.second <= p2.second);
}
不提供严格弱排序,因为将 2 个元素 e1
和 e2
与相同的 .second
进行比较将 return 对于 为真 e1 < e2
和 e2 < e1
都是不允许的。在排序中使用此 compare
函数会调用未定义的行为,可能导致段错误。
您需要执行以下操作:
bool compare(const pair<pair<int, int>, int> &p1, const pair<pair<int, int>, int> &p2){
return p1.second < p2.second;
}