Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Maybee you could try a <a href="http://en.wikipedia.org/wiki/Greedy_algorithm" rel="nofollow">greedy</a> algorithm:</p> <pre><code>1. Create a list sortedList that stores each pair of nodes i and j and is sorted by the weight w(i,j). 2. Create a HashSet connectedNodes that is empty at the beginning 3. while (connectedNodes.size() &lt; n) element := first element of sortedList if (connectedNodes.isEmpty()) connectedNodes.put(element.nodeI); connectedNodes.put(element.nodeJ); delete element from sortedList else for(element in sortedList) //start again with the first if(connectedNodes.get(element.nodeI) || connectedNodes.get(element.nodeJ)) if(!(connectedNodes.get(element.nodeI) &amp;&amp; connectedNodes.get(element.nodeJ))) //so it does not include already both nodes connectedNodes.put(element.nodeI); connectedNodes.put(element.nodeJ); delete element from sortedList break; else continue; </code></pre> <p>So I explain step 3 a little bit:</p> <p>You add as long nodes till all nodes are connected to one other. It is sure that the graph is connected, because you just add a node, if he has a connection to an other one already in the <code>connectedNodes</code> list.</p> <p>So this algorithm is greedy what means, it does not make sure, that the solution is optimal. But it is a quite good approximation, because it always takes the shortest edge (because <code>sortedList</code> is sorted by the weight of the edge). </p> <p>Yo don't get <code>duplicates</code> in <code>connectedNodes</code>, because it is a <code>HashSet</code>, which also make the runtime faster.</p> <p>All in all the runtime should be O(n^2) for the sorting at the beginning and below its around O(n^3), because in worst case you run in every step through the whole list that has size of n^2 and you do it n times, because you add one element in each step.</p> <p>But more likely is, that you find an element much faster than O(n^2), i think in most cases it is O(n).</p>
    singulars
    1. This table or related slice is empty.
    1. POConnecting a Set of Vertices into an optimally weighted graph
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAlex VII
    1. USAlex VII
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COIf I'm not mistaken this solution is [Prim's algorithm](http://en.wikipedia.org/wiki/Prim%27s_algorithm), please always make the necessary references
      singulars
      1. PO
      1. USluiso1979
    2. COI'm not sure.. jut thought how I would do it. Maybee I had this one on the back of my head :D
      singulars
      1. PO
      1. USAlex VII
 

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