StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h1>Pointers enable efficient composite data structures</h1> <p>You have something like this (using pseudocode C++):</p> <pre><code>class Node bool visited double key Node* pi vector<pair<Node*, double>> adjacent //adjacent nodes and edge weights //and extra fields needed for PriorityQueue data structure // - a clean way to do this is to use CRTP for defining the base // PriorityQueue node class, then inherit your graph node from that class Graph vector<Node*> vertices </code></pre> <p>CRTP: <a href="http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern" rel="nofollow">http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern</a></p> <p><strong>The priority queue <code>Q</code> in the algorithm contains items of type <code>Node*</code></strong>, where <code>ExtractMin</code> gets you the <code>Node*</code> with minimum <code>key</code>.</p> <p>The reason <strong>you don't have to do any linear search</strong> is because, when you get <code>u = ExtractMin(Q)</code>, you have a <code>Node*</code>. So <code>u->adjacent</code> gets you both the <code>v</code>'s in <code>G.Adj[u]</code> and the <code>w(u,v)</code>'s in <strong>const time per adjacent node</strong>. Since you have a pointer <code>v</code> to the priority queue node (which <em>is</em> <code>v</code>), you can update it's position in the priority queue in <strong>logarithmic time per adjacent node</strong> (with most implementations of a priority queue).</p> <p><em>To name some specific data structures, the <code>DecreaseKey(Q, v)</code> function used below has logarithmic complexity for Fibonnaci heaps and pairing heaps (amortized).</em></p> <ul> <li>Pairing heap: <a href="http://en.wikipedia.org/wiki/Pairing_heap" rel="nofollow">http://en.wikipedia.org/wiki/Pairing_heap</a> <ul> <li>Not too hard to code yourself - Wikipedia has most of the source code</li> </ul></li> <li>Fibonacci heap: <a href="http://en.wikipedia.org/wiki/Fibonacci_heap" rel="nofollow">http://en.wikipedia.org/wiki/Fibonacci_heap</a></li> </ul> <h1>More-concrete pseudocode for the algorithm</h1> <pre><code>MstPrim(Graph* G) for each u in G->vertices u->visited = false u->key = infinity u->pi = NULL Q = PriorityQueue(G->vertices) while Q not empty u = ExtractMin(Q) u->visited = true for each (v, w) in u->adjacent if not v->visited and w < v->key v->pi = u v->key = w DecreasedKey(Q, v) //O(log n) </code></pre>

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