错误使用Kruskal算法发现的最小值生成树 [英] Bug in finding mininum spanning tree using Kruskal's algorithm
问题描述
我写的code，从增加顶点成为图形和更新边的权重，然后找出最小生成树。我想我已经做到了，但似乎有它的一些错误，但我不能找到它out.The系统使用Valgrind的，并表明，MST的呼唤无效写尺寸4和无效的读取大小为4 ，但我认为它的工作Valgrind的的罚款。整个误差<一个href="https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing" rel="nofollow">https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing
下面code被称为像
CreateNewGraph（）;
AddEdge（1,2，10）;
AddEdge（2,4，10）;
AddEdge（1，3，100）;
AddEdge（3,4，10）;
GetMST（mst_edges）;
和结果将是（1,2）（2,4）（3,4）
和通话
UpdateEdge（1，3，0.1）;
GetMST（mst_edges）;
和结果将是（1,2）（1,3）（2,4）
有被发送到系统来执行，这将被称为像以上，但在很多时间周期以上的
你能不能帮我找出其中的错误，并指出来，并修复它？
的#include＆LT;载体＆GT;
＃包括＆LT;实用＆GT;
＃包括＆LT;算法＆GT;
使用名字空间std;
命名空间的家庭作业{
类边缘{
上市：
边缘（无符号整数，无符号整型，双）;
无符号整型U;
无符号整型伏;
双瓦;
朋友布尔运算符＆LT;（常量边及放大器;一，常量边缘和b）{
返回A.W＆LT; b.w;
}
};
边缘::边（unsigned int类型源= 0，无符号整型目的地= 0，双体重= 0.0）{
U =来源;
V =目的地;
W =体重;
}
矢量＆lt;边缘＆GT;图（0）;
矢量＆lt; int的＆GT;父（0）;
INT findset（INT X）{
如果（！X =父[X]）母公司[X] = findset（父[X]）;
返回父[X]
}
无效CreateNewGraph（）{
graph.clear（）;
parent.clear（）;
}
无效AddEdge（无符号整数U，unsigned int类型V，双W）{
graph.push_back（边（U，V，W））;
}
无效UpdateEdge（无符号整数U，unsigned int类型V，双W）{
的for（int i = 0; I＆LT; graph.size（）;我++）{
如果（图[我] .U == U＆功放;＆放大器;图[我] .V == V）图[我] =边缘（U，V，W）;
}
}
无效GetMST（矢量＆lt;对＆LT;为unsigned int，unsigned int类型＆GT;＆GT;＆安培; mst_edges）{
mst_edges.clear（）;
parent.clear（）;
INT E = graph.size（）;
的for（int i = 0; I＆LT; = E + 1;我++）parent.push_back（我）;
stable_sort（graph.begin（），graph.end（））;
的for（int i = 0; I＆其中，E，我++）{
// cout的＆LT;＆LT;图[我] .U＆LT;＆LT; ：＆其中;＆其中;图[我] .V＆LT;＆LT; ：＆其中;＆其中;图[我] .W＆LT;＆LT; ：＆其中;＆其中;父[I + 1];＆其中; ENDL;
INT PU = findset（图[我] .U）;
INT PV = findset（图[我] .V）;
如果（PU！= PV）{
父[PU] =父[光伏]
mst_edges.push_back（make_pair（图[我] .U，图[我] .V））;
}
}
}
无效的init（）{
}
无效清除（）{
}
}
我认为这个问题是你如何设置父指针。请注意，您已经设置了家长为
的for（int i = 0; I＆LT; = E + 1;我++）parent.push_back（我）;
这会在父阵列一个条目的每个边的图形，加上一个额外的之一。然而，每个节点的具有父，而不是每一个的边缘的，并在图中节点的数量可以是大于边加一的数量。例如，假设你给这个边集：
1 2
3 4
5 6
该图清楚地中有六个节点（编号为1 ... 6），但你的code只会使家长4项空间。
试着改变你的code，这样你设置家长是合适的大小，可能是通过寻找最大和最小编号的节点边的名单和尺寸数组恰当。另外，考虑使用的std :: unordered_map＆LT; INT，INT＆GT; ，这是比较灵活的，如果顶点号不连续地从0开始，
希望这有助于！
I write the code from adding vertex into a graph and update the weight of edge and then find the minimum spanning tree. I think that I have done it but there seems to be some error in it but I cannot find it out.The system using Valgrind and indicate that "invalid write of size 4" and "invalid read of size 4 " in the call of MST, but I think it work fine.The whole error of Valgrind is https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing
The following code is called by like
CreateNewGraph();
AddEdge(1, 2, 10);
AddEdge(2, 4, 10);
AddEdge(1, 3, 100);
AddEdge(3, 4, 10);
GetMST(mst_edges);
and the result will be (1,2) (2,4) (3,4).
and call
UpdateEdge(1, 3, 0.1);
GetMST(mst_edges);
and the result will be (1,2) (1,3) (2,4).
It is sent to a system to execute and it will be called like above but in a lot of time cycle above.
Can you help me to figure out where is the bug and point it out and fix it?
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
namespace HOMEWORK{
class Edge{
public:
Edge(unsigned int, unsigned int, double);
unsigned int u;
unsigned int v;
double w;
friend bool operator<(const Edge& a, const Edge& b){
return a.w < b.w;
}
};
Edge::Edge(unsigned int source = 0, unsigned int destination = 0, double weight = 0.0){
u = source;
v = destination;
w = weight;
}
vector<Edge> graph(0);
vector<int> parent(0);
int findset(int x){
if(x != parent[x])parent[x] = findset(parent[x]);
return parent[x];
}
void CreateNewGraph(){
graph.clear();
parent.clear();
}
void AddEdge(unsigned int u, unsigned int v, double w){
graph.push_back(Edge(u,v,w));
}
void UpdateEdge(unsigned int u, unsigned int v, double w){
for(int i = 0; i < graph.size(); i ++){
if(graph[i].u == u && graph[i].v == v)graph[i] = Edge(u,v,w);
}
}
void GetMST(vector<pair<unsigned int, unsigned int> >& mst_edges){
mst_edges.clear();
parent.clear();
int e = graph.size();
for(int i = 0; i <= e + 1; i ++)parent.push_back(i);
stable_sort(graph.begin(), graph.end());
for(int i = 0; i < e; i ++){
//cout << graph[i].u << ":" << graph[i].v << ":" << graph[i].w << ":" << parent[i + 1] << endl;
int pu = findset(graph[i].u);
int pv = findset(graph[i].v);
if(pu != pv){
parent[pu] = parent[pv];
mst_edges.push_back(make_pair(graph[i].u, graph[i].v));
}
}
}
void Init(){
}
void Cleanup(){
}
}
I think the issue is how you're setting up parent pointers. Note that you've set up parents as
for(int i = 0; i <= e + 1; i ++) parent.push_back(i);
This creates one entry in the parent array for each edge in the graph, plus one extra one. However, each node has a parent, not each edge, and the number of nodes in a graph can be bigger than the number of edges plus one. For example, suppose you're given this set of edges:
1 2
3 4
5 6
This graph clearly has six nodes in it (numbered 1 ... 6), but your code would only make space for 4 entries in parents.
Try changing your code so that you set parents to be the proper size, probably by finding the maximum and minimum numbered node in the list of edges and sizing the array appropriately. Alternatively, consider using a std::unordered_map<int, int>, which is more flexible if the vertex numbers don't contiguously begin at 0.
Hope this helps!
这篇关于错误使用Kruskal算法发现的最小值生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
