我想在文件中的图上运行prim，但对于某些输入，prim_minimum_spanning_tree会导致分段错误。当我用valgrind运行它时，segfault不会发生，但valgrind表示存在错误("大小为8的无效读取"(，但它只在某些图表上显示错误。
我对使用boost非常陌生，我怀疑我对图形的初始化是错误的。
std::pair<int,int> *edges = new std::pair<int,int>[num_edges];
double *weights = new double[num_edges];
// read edges and weights into arrays
readin(argc, argv, edges, weights);
typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, mat_t>> Graph;
Graph G(num_nodes);
for(int i = 0; i < num_edges; i++){
// check input
assert(edges[i].first >= 0 && "zero first");
assert(edges[i].first < num_nodes && "numvertices first");
assert(edges[i].second >= 0 && "zero second");
assert(edges[i].second < num_nodes && "numvertices second");
// add edge
auto edge_iterator = add_edge( edges[i].first,edges[i].second, weights[i], G);
}
//create parent vector to store solution
std::vector<graph_traits<Graph>::vertex_descriptor> *parents =
new std::vector<graph_traits<Graph>::vertex_descriptor>(num_vertices(G));
//run prim
prim_minimum_spanning_tree(G, &(parents->at(0)));
delete parents;
delete[] edges;
delete[] weights;
我试着用gdb调试它，但找不到错误。。。
更新：谢谢你的帮助！
我终于发现了这个错误：它与readin函数无关。问题是，当图包含自循环时，prim-in-boost不起作用。。。(或者至少只有当错误发生时(
从boost文档："Boost.Graph中实现的算法无法在具有平行边的图上产生正确的结果">
我不认为segfault被视为"；不正确的结果"；。。。
正如评论者所说，修复你的valgrind错误。很可能您在readin函数中做了超出范围的事情。
你操作的原始指针太多了。这不是C，为什么要假装是呢？
以下是我对它的看法，没有使用手动分配，也没有潜在的错误边界。请注意，我确保输入是无符号的，这样我们就不会得到混合符号整数比较。这也使得一半的输入检查是多余的：
//assert(s >= 0 && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0 && "zero target");
assert(t < num_vertices(G) && "numvertices target");
Wandbox直播
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
#include <fstream>
using mat_t = double;
struct input { unsigned source, target; mat_t weight; };
static auto readin(std::string filename) {
std::vector<input> lines;
input line;
std::ifstream ifs(filename);
while (ifs >> line.source >> line.target >> line.weight) {
lines.push_back(line);
}
return lines;
}
int main() {
// read edges and weights into arrays
auto input = readin("input.txt");
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, mat_t>>;
unsigned highest_vertex = 0;
for (auto [s,t,w]: input)
highest_vertex = std::max({highest_vertex, s, t});
Graph G(highest_vertex + 1);
for (auto [s,t,w]: input) {
//assert(s >= 0 && "zero source");
assert(s < num_vertices(G) && "numvertices source");
//assert(t >= 0 && "zero target");
assert(t < num_vertices(G) && "numvertices target");
// add edge
add_edge(s, t, w, G);
}
//create parent vector to store solution
std::vector<Graph::vertex_descriptor> parents(num_vertices(G));
//run prim
prim_minimum_spanning_tree(G, parents.data());
print_graph(G);
}
基于input.txt的文档示例：
0 2 0.1
1 3 0.1
1 4 0.2
2 1 0.7
2 3 0.3
3 4 0.1
4 0 0.1
打印：
0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0
并在-fsanitize=undefined,address和valgrind下运行完全干净。也没有内存泄漏：
==9025== Memcheck, a memory error detector
==9025== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9025== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9025== Command: ./sotest
==9025==
0 <--> 2 4
1 <--> 3 4 2
2 <--> 0 1 3
3 <--> 1 2 4
4 <--> 1 3 0
==9025==
==9025== HEAP SUMMARY:
==9025== in use at exit: 0 bytes in 0 blocks
==9025== total heap usage: 46 allocs, 46 frees, 84,314 bytes allocated
==9025==
==9025== All heap blocks were freed -- no leaks are possible
==9025==
==9025== For counts of detected and suppressed errors, rerun with: -v
==9025== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)