Databases
StackOverflow2013
Postsdbo
POO(1) Make, Find, Union in Disjoint Sets Data Structure
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POO(1) Make, Find, Union in Disjoint Sets Data Structure
    text
    copied!<p>Today, I had discussion with someone about Kruskal Minimum Spanning Tree algorithm because of page 13 of <a href="http://ww3.algorithmdesign.net/handouts/MST.pdf" rel="nofollow noreferrer">this slide</a>. </p> <p>The author of the presentation said that if we implement disjoint sets using (doubly) linked list, the performance for <strong>Make</strong> and <strong>Find</strong> will be <strong>O(1)</strong> and <strong>O(1)</strong> respectively. The time for operation <strong>Union(u,v)</strong> is <strong>min(nu,nv)</strong>, where <strong>nu</strong> and <strong>nv</strong> are the sizes of the sets storing u and v.</p> <p>I said that we can improve the time for the <strong>Union(u,v)</strong> to be <strong>O(1)</strong> by making the representation pointer of each member pointing a locator that contains the pointer to the real representation of the set. </p> <p>In Java, the data structure would look like this :</p> <pre><code>class DisjointSet { LinkedList&lt;Vertex&gt; list = new LinkedList&lt;Vertex&gt;(); // for holding the members, we might need it for print static Member makeSet(Vertex v) { Member m = new Member(); DisjointSet set = new DisjointSet(); m.set = set; set.list.add(m); m.vertex = v; Locator loc = new Locator(); loc.representation = m; m.locator = loc; return m; } } class Member { DisjointSet set; Locator locator; Vertex vertex; Member find() { return locator.representation; } void union(Member u, Member v) { // assume nv is less than nu u.set.list.append(v.set.list); // hypothetical method, append a list in O(1) v.set = u.set; v.locator.representation = u.locator.representation; } } class Locator { Member representation; } </code></pre> <p>Sorry for the minimalistic code. If it can be made this way, than running time for every disjoint set operation (<strong>Make,Find,Union</strong>) will be <strong>O(1)</strong>. But the one whom I had discussion with can't see the improvement. I would like to know your opinion on this.</p> <p>And also what is the fastest performance of Find/Union in various implementations? I'm not an expert in data structure, but by quick browsing on the internet I found out there is no constant time data structure or algorithm to do this.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload