我的最小生成樹實現中的錯誤

我試圖實現克魯斯卡爾算法，該算法在無向加權圖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

我的最小生成樹實現中的錯誤

回答

相關問題