我的最小生成树实现中的错误

我试图实现克鲁斯卡尔算法，该算法在无向加权图G（V，E）处找到最小生成树。我的实现使用不相交集来使算法更快。这里是代码：我的最小生成树实现中的错误

#include <stdio.h> 
#include <vector> 
#include <algorithm> 

using std::sort; 
using std::vector; 

const int MAXV = 1000; 

struct set_union { 
    set_union *parent; 
    int rank; 
} *array[MAXV]; 

set_union* make_set() { 
    set_union *ret = new set_union(); 
    ret->parent = NULL; 
    ret->rank = 1; 
    return ret; 
} 

set_union* find_root(set_union *u) { 
    set_union *temp = u; 
    while(temp->parent != NULL) { 
    temp = temp->parent; 
    } 
    return temp; 
} 

void union_sets(set_union *&pa, set_union *&pb) { 
    set_union *a = find_root(pa), *b = find_root(pb); 
    if(a->rank > b->rank) { 
    b->parent = a; 
    } else if(a->rank < b->rank) { 
    a->parent = b; 
    } else { 
    a->parent = b; 
    a->rank++; 
    } 
} 

bool same_component(set_union *a, set_union *b) { 
    return find_root(a) == find_root(b); 
} 

struct link { 
    int v; 
    int w; 
}; 

struct edge { 
    int v,u; 
    int w; 
}; 

bool operator < (const edge& a, const edge& b) { 
    if(a.w < b.w) { return true; } 
    else { return false; } 
} 

struct graph { 
    vector<vector<link> > adj; 
    vector<edge> edges; 
    int V,E; 
    graph(int v) : adj(v), edges(0), V(v), E(0) {} 
}; 

void insert(graph &g, int a, int b, int c = 1) { 
    g.edges.push_back((edge) {a,b,c}); 
    g.adj[a].push_back((link) {b,c}); 
    g.adj[b].push_back((link) {a,c}); 
} 

void kruskal(graph g, vector<edge> &tree) { 
    printf("Entering kruskal\n"); 
    tree.clear(); 
    for(int i = 0; i < g.V; i++) { 
    array[i] = make_set(); 
    } 

    printf("sorting edges by weight\n"); 
    sort(g.edges.begin(), g.edges.end()); 
    int i; 

    printf("Entering while\n"); 
    while(tree.size() < g.V-1 && i < g.E) { 
    if(!same_component(array[g.edges[i].v], array[g.edges[i].u])) { /* Here is the error */ 
     tree.push_back(g.edges[i]); 
     union_sets(array[g.edges[i].v], array[g.edges[i].u]); 
    } 
    i++; 
    } 
    printf("Exiting kruskal\n"); 
} 


int main(void) { 
    int v,e; 
    scanf("%d %d", &v, &e); 

    graph g(v); 

    for (int i = 0; i < e; ++i) { 
    int a,b,c; 
    scanf("%d %d %d", &a, &b, &c); 
    insert(g,a,b,c); 
    } 

    vector<edge> tree; 
    kruskal(g,tree); 

    for (vector<edge >::iterator it = tree.begin(); it < tree.end(); ++it) { 
    printf("%d %d w = %d\n", it->v, it->u, it->w); 
    } 

    return 0; 
}

它编译没有错误，但它没有给我结果。例如，当我给它输入时：

它根本不会产生任何输出。谁能帮我？提前致谢。

编辑：我发现我认为错误与评论的位置。由于tree为空，因此我得出结论if(!same_component(array[g.edges[i].v], array[g.edges[i].u]))总是false。所以这个错误必须在same_component函数中，但我无法发现它。

来源

2012-07-15 Rontogiannis Aristofanis

要求陌生人通过检查发现代码中的错误并不是富有成效的。您应该使用调试器或打印语句来识别（或至少隔离）问题，然后回来一个更具体的问题（一旦您将其缩小到10行[测试案例]（http：///sscce.org））。 – 2012-07-15 17:28:56

'printf'？ 'scanf'？ 'MAGIC_BUFFER_SIZE'？ EWWW。我不会猜测*那*中的错误。 – Puppy 2012-07-15 17:29:25

@Oli Charlesworth我在论文中运行程序，输出结果是正确的。该错误不在算法中，而是在'set_union'实现中。 – 2012-07-15 17:35:52

在kruskal()函数中，在测试其值while(tree.size() < g.V-1 && i < g.E)之前，您未初始化i。它将包含垃圾（无论是在已经存储的内容中），这可能会导致循环不执行一次。

来源

2012-07-15 17:57:06

你是绝对正确的，但是当我执行程序时，它给了我正确的答案，而不需要初始化'i'。但是你说得对，我应该初始化它 – 2012-07-16 09:47:29

@RondogiannisAristophanes：我猜你已经“幸运”了，“i”背后的记忆恰好已经是0或者一些很低的数字了。一些编译器（例如带'/ RTCs'选项的MSVC++ - 也可以参见'/ RTCu'）允许堆栈内存填充“不太可能”的值来帮助找到这些错误。 – 2012-07-16 11:48:40

错误出现在insert函数中。当我在图上插入边时，我不会增加图的边的总数。所以Kruscal函数的while循环从不执行。

来源

2012-07-15 17:53:36

我的最小生成树实现中的错误

回答

相关问题