Bug in my Minimum Spanning Tree implementation [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 8 years ago.

I'm trying to implement the kruskal's algorithm which finds the minimum spanning tree at a undirected, weighted graph G(V,E). My implementation uses disjoint sets to make the algorithm faster. Here is the code:

#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;
}

It compiles without errors, but it gives me no results. For example when I give it this input:

3 3
0 1 1
1 2 1
2 0 2

it doesn't produce any output at all. Can anyone help me? Thanks in advance.

Edit: I have spotted where I think the error is with a comment. As the tree is empty, I conclude that if(!same_component(array[g.edges[i].v], array[g.edges[i].u])) is always false. So the mistake must be at the same_component function, but I cannot spot it.

Answer 1

In the kruskal() function, you aren't initialising i before testing its value with while(tree.size() < g.V-1 && i < g.E). It will contain rubbish (whatever was in already memory), which will probably cause the loop not to execute even once.

Answer 2

The error is at the insert function. When I insert an edge at the graph, I don't increase the total number of the graph's edges. So the while loop at the Kruscal function never executes.