Я просмотрел другие подобные вопросы, но не смог выяснить причину этой ошибки. Я пишу программу на C ++ для реализации алгоритма Kruskal Minimum Spanning Tree с использованием объединения по рангу со сжатием пути.
Он печатает края 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 / class:
(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
Может кто-нибудь объяснить, что ломается, когда я включаю сжатие пути в цикле?
редактировать: пример ввода, который дает ошибку:
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
Есть только 10 узлов, но есть 9-10 ребер и 10-7 ребер, поэтому вы получили доступ за пределы вектора. Попробуйте преобразовать вход 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;
Других решений пока нет …