时间:2018-01-08 标签:c++free(): invalid pointer error while path compression (union by rank)

Question

我查看了其他类似的问题，但无法找出导致此错误的原因。我正在编写一个 C++ 程序来使用 Union by rank 和路径压缩来实现 Kruskal 的最小生成树算法。它正确打印 MST 的边缘，但包括路径压缩部分会导致此错误:

* `./kruskal' 中的错误:free():无效指针:0x0000000001650d00 *

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int,int> > pip;
typedef pair<int,int> pii;
class UnionFind {
    vector <int> parent,rank;
    public:
        UnionFind(int n){
            parent.resize(n);
            rank.resize(n);
            for (int i=0;i<n;i++) { //initialize all parents and ranks
                parent[i]=i;
                rank[i]=0;
            }
        }
        int find (int x){
            int root=x,y;
            while (parent[root]!=root) {
                root=parent[root];
            }
//uncommenting the following loop gives the error
            /*while (parent[x]!=root){ //path compression
                y=parent[x];
                parent[x]=root;
                x=y;
            }*/
            return root;
        }
        void unite (int x,int y) {
            x=find(x);
            y=find(y);
            if (rank[x]>=rank[y]){
                parent[y]=x;
                if (rank[x]==rank[y])
                    rank[x]++;
            }
            else parent[x]=y;
        }
};
int main() {
    int v1,v2,w,n,m;
    cout<<"Enter number of vertices, edges: ";
    cin>>n>>m;
    vector <pip> edges(m);
    UnionFind uf(n);
    cout<<"Enter edges in the form v1,v2,w: ";//w=length of edge
    for (int i=0;i<m;i++) {
        cin>>v1>>v2>>w;
        edges[i]=pip(w,pii(v1,v2));
    }
    sort (edges.begin(),edges.end()); //sort edges in increasing order or lengths
    cout<<"MST: edges \n";
    for (int i=0;i<m;i++){
        if (uf.find(edges[i].second.first)!=uf.find(edges[i].second.second)) {
            uf.unite (edges[i].second.first,edges[i].second.second);
            cout<<edges[i].second.first<<"--"<<edges[i].second.second<<endl;
        }
    }
    return 0;
}

通过查看 gdb 的回溯，它似乎是 vector/类析构函数的问题:

(gdb) backtrace
#0  0x00007ffff74ab267 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:55
#1  0x00007ffff74aceca in __GI_abort () at abort.c:89
#2  0x00007ffff74eebf3 in __libc_message (do_abort=do_abort@entry=1, 
    fmt=fmt@entry=0x7ffff7607168 "*** Error in `%s': %s: 0x%s ***\n")
    at ../sysdeps/posix/libc_fatal.c:175
#3  0x00007ffff74f6c09 in malloc_printerr (ptr=<optimized out>, 
    str=0x7ffff76032ba "free(): invalid pointer", action=1) at malloc.c:4965
#4  _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:3834
#5  0x00007ffff74fa83c in __GI___libc_free (mem=<optimized out>) at malloc.c:2950
#6  0x0000000000402cfc in __gnu_cxx::new_allocator<int>::deallocate (this=0x7fffffffdf58, 
    __p=0x618d00) at /usr/include/c++/5/ext/new_allocator.h:110
#7  0x0000000000402588 in __gnu_cxx::__alloc_traits<std::allocator<int> >::deallocate (__a=..., 
    __p=0x618d00, __n=10) at /usr/include/c++/5/ext/alloc_traits.h:185
#8  0x0000000000401ce6 in std::_Vector_base<int, std::allocator<int> >::_M_deallocate (
    this=0x7fffffffdf58, __p=0x618d00, __n=10) at /usr/include/c++/5/bits/stl_vector.h:178
#9  0x00000000004018a8 in std::_Vector_base<int, std::allocator<int> >::~_Vector_base (
    this=0x7fffffffdf58, __in_chrg=<optimized out>) at /usr/include/c++/5/bits/stl_vector.h:160
#10 0x0000000000401498 in std::vector<int, std::allocator<int> >::~vector (this=0x7fffffffdf58, 
    __in_chrg=<optimized out>) at /usr/include/c++/5/bits/stl_vector.h:425
#11 0x000000000040140b in UnionFind::~UnionFind (this=0x7fffffffdf40, __in_chrg=<optimized out>)
    at kruskal.cpp:7
#12 0x0000000000401023 in main () at kruskal.cpp:47

有人可以解释一下当我在 while 循环中包含路径压缩时有什么中断吗？

编辑:给出错误的示例输入:

10 14
1 5 1
1 8 10
2 3 2
4 1 4
4 8 1
5 6 3
6 2 1
6 3 3
6 7 7
6 9 1
8 5 5
8 9 9
9 10 2
10 7 1

Answer 1

只有10个节点，但有9-10条边和10-7条边，所以你访问了 vector 的范围之外。在存储之前尝试将 1-origin 输入转换为 0-origin。

尝试

for (int i=0;i<m;i++) {
    cin>>v1>>v2>>w;
    edges[i]=pip(w,pii(v1-1,v2-1));
}

代替

for (int i=0;i<m;i++) {
    cin>>v1>>v2>>w;
    edges[i]=pip(w,pii(v1,v2));
}

和

cout<<(edges[i].second.first+1)<<"--"<<(edges[i].second.second+1)<<endl;

代替

cout<<edges[i].second.first<<"--"<<edges[i].second.second<<endl;