0

我正在尝试实现 kruskal 算法，该算法在无向加权图 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;
}

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

3 3
0 1 1
1 2 1
2 0 2

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

编辑：我发现我认为错误在哪里，并带有评论。由于tree是空的，我的结论if(!same_component(array[g.edges[i].v], array[g.edges[i].u]))是总是false。所以错误一定出在same_component函数上，但我无法发现它。

4

2 回答 2

2

在kruskal()函数中，i在使用while(tree.size() < g.V-1 && i < g.E). 它将包含垃圾（无论是在内存中的什么），这可能会导致循环甚至不执行一次。

于 2012-07-15T17:57:06.997 回答
1

错误在于insert函数。当我在图形上插入一条边时，我不会增加图形边的总数。所以 Kruscal 函数的 while 循环永远不会执行。

于 2012-07-15T17:53:36.003 回答