0

無向重み付きグラフ 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]))falsesame_component

4

2 に答える 2

2

このkruskal()関数ではi、値をでテストする前に初期化を行っていませんwhile(tree.size() < g.V-1 && i < g.E)。ゴミ（すでにメモリにあるものは何でも）が含まれているため、ループが1回も実行されない可能性があります。

于 2012-07-15T17:57:06.997 に答える
1

エラーはinsert関数にあります。グラフにエッジを挿入するとき、グラフのエッジの総数を増やしません。したがって、Kruscal関数のwhileループは実行されません。

于 2012-07-15T17:53:36.003 に答える