title: Boruvka algorithm Minimum Spanning Tree for Directed Graphs
body: <p>Does the Boruvka algorithm (http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm) only work for undirected graphs?</p>
  
  <p>For example, if we have a graph structure that looks like:</p>
  
  <pre><code>node 1 -&gt; node 2 (weight 1), node 3 (weight 1), node 4 (weight 1)
  
  node 2 -&gt; node 3 (weight 2)
  
  node 3 -&gt; node 4 (weight 2)
  
  node 4 -&gt; node 2 (weight 2)
  </code></pre>
  
  <p>Then the minimum spanning tree should include the edges:</p>
  
  <pre><code>1 -&gt; 2
  
  1 -&gt; 3
  
  1 -&gt; 4
  </code></pre>
  
  <p>However, Boruvka's algorithm will spit out </p>
  
  <pre><code>1 -&gt; 2
  
  2 -&gt; 3
  
  3 -&gt; 4
  </code></pre>
  
  <p>Because, Boruvka first looks at each individual node and adds the shortest edge outgoing from that node to the MST.</p>
  
  <p>I know in the wikipedia article it says that edge weights have to be distinct but as long as all of the edge weights coming out of node 1 are less than the "outer" edge weights (from nodes 2-4) then it seems like Boruvka's algorithm fails. Is this because it is a directed graph not undirected?</p>