StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To check for circuits, you'll want to use a union-find data structure. The easiest way to do it is just with linked lists, but there are more efficient implementations. This link can help you if you want to implement one yourself.</p> <p><a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow">http://en.wikipedia.org/wiki/Disjoint-set_data_structure</a></p> <p>Or here's a link to a java implementation:</p> <p><a href="http://www.koders.com/java/fid125D835ECD1C1C701008C456A93A7179FA06D196.aspx" rel="nofollow">http://www.koders.com/java/fid125D835ECD1C1C701008C456A93A7179FA06D196.aspx</a></p> <p>Basically, a union-find data structure allows you to track disjoint sets of elements, and supports two operations:</p> <pre><code>1) Find, which takes an element as an argument and tells you which set it is in 2) Union, which takes 2 disjoint sets and merges them </code></pre> <p>Let's say your array of edges that will form the MST is <code>S</code>. The idea is that you can make a set, <code>C</code>, using Union-Find, that tracks which vertices of the graph are connected by the edges in <code>S</code>. When <code>C</code> contains all the vertices in the graph, then you're finished, and checking to see if the addition of an edge will create a cycle amounts to checking whether the two vertices that it connects are already in <code>C</code> (by using two <code>Find</code> operations).</p> <p>So if <code>E</code> is the set of all the edges in the graph, your update operation can proceed like so:</p> <pre><code> Remove edge, e from E, with minimum weight (say that it connects vertices v1 and v2) Find(v1) and Find(v2) If v1 and v2 are both in C then continue Else, Union(C,{v1,v2}) and append e to S </code></pre> <p>And you stop the update once <code>C</code> contains every vertex of the graph.</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