Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Kruskall's algorithm won't searches for cycles, because It's not performance efficient; But tries to create a components which are tree, and then connect them to each other. As you know if you connect two different trees with one new edge you will create new tree and there is no need to check for cycles.</p> <p>If you look at <a href="http://en.wikipedia.org/wiki/Kruskal%27s_algorithm" rel="nofollow">wiki page</a> algorithm is as follow:</p> <pre><code>1. create a forest F (a set of trees), where each vertex in the graph is a separate tree 2. create a set S containing all the edges in the graph 3. while S is nonempty and F is not yet spanning a. remove an edge with minimum weight from S b. if that edge connects two different trees, then add it to the forest, combining two trees into a single tree c. otherwise discard that edge. </code></pre> <p>You should use <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow">Disjoint Set Data Structure</a> for this. again from wiki:</p> <blockquote> <p>first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step "remove an edge with minimum weight from S" to operate in constant time. Next, we use a disjoint-set data structure (Union&amp;Find) to keep track of which vertices are in which components. We need to perform O(E) operations, two 'find' operations and possibly one union for each edge. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(E) operations in O(E log V) time. Thus the total time is O(E log E) = O(E log V).</p> </blockquote> <hr> <h1>Creating Disjoint Forests</h1> <p>Now you can take a look at <a href="http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/incremental_components.html" rel="nofollow">Boost Graph Library-Incremental Components</a> part. You should implement some methods: <strong>MakeSet</strong>, <strong>Find</strong>, <strong>Union</strong>, After that you can implement kruskall's algorithm. All you doing is working with some sets, and simplest possible way to do so is using linked list.</p> <p>Each set has one element named as <strong>representative element</strong> which is first element in the set.</p> <p>1- First implement <strong>MakeSet</strong> by linked lists:</p> <blockquote> <p>This prepares the disjoint-sets data structure for the incremental connected components algorithm by making each vertex in the graph a member of its own component (or set).</p> </blockquote> <p>You should just initialize each vertex (element) as a representative element of new set, you can do this by setting them as themselves parent:</p> <pre><code> function MakeSet(x) x.parent := x </code></pre> <p>2- Implement <strong>Find</strong> method:</p> <p>Find representative element of set which contains vertex <code>x</code>:</p> <pre><code> function Find(x) if x.parent == x return x else return Find(x.parent) </code></pre> <p>The <code>if</code> part checks the element is representative element or not. we set all representative elements of sets as their first element by setting them as themselves parent.</p> <p>3- And finally when you got all previous things simple part is implementing <strong>Union</strong> method:</p> <pre><code>function Union(x, y) xRoot := Find(x) // find representative element of first element(set) yRoot := Find(y) // find representative element of second element(set) xRoot.parent := yRoot // set representative element of first set // as same as representative element of second set </code></pre> <p>Now how you should run Kruskall?</p> <p>First put all nodes in <code>n</code> disjoint sets by <strong>MakeSet</strong> method. In each step after finding desired edge (not checked and minimal one), find related sets of its endpoint vertices by <strong>Find</strong> method (their representative elements), if they are same, drop this edge out because this edge causes a cycle, but If they are in different sets, use <strong>Union</strong> method to merge these sets. Because each set is tree union of them is tree.</p> <p>You can optimize this by choosing better data structure for disjoint sets, but for now I think is enough. If you are interested in more advanced data structures, you can implement <strong>rank</strong> base way, you will find it in wiki, It's easy but I didn't mention it to prevent from bewilderment.</p>
    singulars
    1. This table or related slice is empty.
    1. POTesting for a circuit when implementing Kruskalls algorithm
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USSaeed Amiri
    1. USSaeed Amiri
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTesting for a circuit when implementing Kruskalls algorithm
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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