In this problem, we consider implementing the Union-Find data structure using ar

Question

In this problem, we consider implementing the Union-Find data structure using arrays – we have an array Component that maintains the name of the set containing each element. Let S be a set containing n elements denoted {1, 2, . . . , n}. The array Component has size n, where Component[s] is the name of the set containing s. To implement MakeSet(S), we set up the array and initialize it to Component[s] = s, for each s in S. In this implementation, Find(v) is a simple lookup and takes O(1) time. However, Union(x, y) can take as long as O(n) time, as we have to update the values of all elements in the sets containing x and y. Use the Component array along with some optimizations (which you must describe clearly) to implement Kruskal’s algorithm on a graph G with n vertices and m edges in O(m log n) time.

Explanation / Answer

The following greedy algorithm works for this problem. Start with no edges in the spanning tree. Take the shortest edge and add it to the tree ­ we will use it. Now take the rest of the edges in order of increasing length and add them to the tree as long as they connect two vertices not already connected by the previous edges. Repeat until all vertices are connected. Think of this as growing a forest of trees which get joined together until they become one big spanning tree. Here is an implementation.

int uf[128];

// a structure to represent an edge

struct Edge {

// the two endpoints and the weight

int u, v, w;

// a comparator that sorts by least weight

bool operator<( const Edge &e ) const { return w < e.w; }

};

// the graph represented as a list of edges

Edge edges[100000];

// the number of vertices and the number of edges

int n, m;

int kruskal() {

// sort the first m entries in the 'edges' array

sort( edges, edges + m );

// initialize the union­find array

for( int i = 0; i < n; i++ ) uf[i] = i;

// the number of trees (parties), and the total weight

int trees = n, sum = 0;

for( int i = 0; i < m && trees > 1; i++ )

{

if( UNION( edges[i].u, edges[i].v ) ) {

// use edge i in the tree

trees­--;

sum += edges[i].w;

} }

return sum; }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.