PHP实现克鲁斯卡尔算法

PHP实现的格鲁斯卡尔算法（kruscal），如下代码：

<ol class="dp-c">
<li class="alt"><span><span><?php  </span></span></span></li>
<li><span>    <span class="keyword">require</span><span> </span><span class="string">'edge.php'</span><span>; </span></span></li>
<li class="alt"><span>    <span class="vars">$a</span><span> = </span><span class="keyword">array</span><span>(</span><span class="string">'a'</span><span>, </span><span class="string">'b'</span><span>, </span><span class="string">'c'</span><span>, </span><span class="string">'d'</span><span>, </span><span class="string">'e'</span><span>, </span><span class="string">'f'</span><span>, </span><span class="string">'g'</span><span>, </span><span class="string">'h'</span><span>, </span><span class="string">'i'</span><span>); </span></span></li>
<li><span>    <span class="vars">$b</span><span> = </span><span class="keyword">array</span><span>(</span><span class="string">'ab'</span><span>=></span><span class="string">'10'</span><span>, </span><span class="string">'af'</span><span>=></span><span class="string">'11'</span><span>, </span><span class="string">'gb'</span><span>=></span><span class="string">'16'</span><span>, </span><span class="string">'fg'</span><span>=></span><span class="string">'17'</span><span>, </span><span class="string">'bc'</span><span>=></span><span class="string">'18'</span><span>, </span><span class="string">'bi'</span><span>=></span><span class="string">'12'</span><span>, </span><span class="string">'ci'</span><span>=></span><span class="string">'8'</span><span>, </span><span class="string">'cd'</span><span>=></span><span class="string">'22'</span><span>, </span><span class="string">'di'</span><span>=></span><span class="string">'21'</span><span>, </span><span class="string">'dg'</span><span>=></span><span class="string">'24'</span><span>, </span><span class="string">'gh'</span><span>=></span><span class="string">'19'</span><span>, </span><span class="string">'dh'</span><span>=></span><span class="string">'16'</span><span>, </span><span class="string">'de'</span><span>=></span><span class="string">'20'</span><span>, </span><span class="string">'eh'</span><span>=></span><span class="string">'7'</span><span>,</span><span class="string">'fe'</span><span>=></span><span class="string">'26'</span><span>); </span></span></li>
<li class="alt"><span>      </span></li>
<li><span>    <span class="vars">$test</span><span> = </span><span class="keyword">new</span><span> Edge(</span><span class="vars">$a</span><span>, </span><span class="vars">$b</span><span>); </span></span></li>
<li class="alt"><span>    print_r(<span class="vars">$test</span><span>->kruscal()); </span></span></li>
<li><span>?> </span></li>
<li class="alt"><span> </span></li>
<li><span><?php   </span></span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="comment">//边集数组的边类</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">class</span><span> EdgeArc{ </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$begin</span><span>;</span><span class="comment">//起始点</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$end</span><span>;</span><span class="comment">//结束点</span><span> </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$weight</span><span>;</span><span class="comment">//权值</span><span> </span></span></li>
<li class="alt"><span> </span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> EdgeArc(</span><span class="vars">$begin</span><span>, </span><span class="vars">$end</span><span>, </span><span class="vars">$weight</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->begin = </span><span class="vars">$begin</span><span>; </span></span></li>
<li><span>            <span class="vars">$this</span><span>-></span><span class="func">end</span><span> = </span><span class="vars">$end</span><span>; </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->weight = </span><span class="vars">$weight</span><span>; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span> </span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getBegin(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->begin; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span> </span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getEnd(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>-></span><span class="func">end</span><span>; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span> </span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getWeight(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->weight; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>    } </span></li>
<li><span> </span></li>
<li class="alt"><span> </span></li>
<li><span><span class="keyword">class</span><span> Edge{ </span></span></li>
<li class="alt"><span>    <span class="comment">//边集数组实现图</span><span> </span></span></li>
<li><span> </span></li>
<li class="alt"><span>    <span class="keyword">private</span><span> </span><span class="vars">$vexs</span><span>;</span><span class="comment">//顶点集合</span><span> </span></span></li>
<li><span>    <span class="keyword">private</span><span> </span><span class="vars">$arc</span><span>;</span><span class="comment">//边集合</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">private</span><span> </span><span class="vars">$arcData</span><span>;</span><span class="comment">//要构建图的边信息</span><span> </span></span></li>
<li><span>    <span class="keyword">private</span><span> </span><span class="vars">$krus</span><span>;</span><span class="comment">//kruscal算法时存放森林信息</span><span> </span></span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> Edge(</span><span class="vars">$vexsData</span><span>, </span><span class="vars">$arcData</span><span>){ </span></span></li>
<li class="alt"><span>        <span class="vars">$this</span><span>->vexs = </span><span class="vars">$vexsData</span><span>; </span></span></li>
<li><span>        <span class="vars">$this</span><span>->arcData = </span><span class="vars">$arcData</span><span>; </span></span></li>
<li class="alt"><span>        <span class="vars">$this</span><span>->createArc(); </span></span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="comment">//创建边</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> createArc(){ </span></span></li>
<li><span>        <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->arcData </span><span class="keyword">as</span><span> </span><span class="vars">$key</span><span>=></span><span class="vars">$value</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$key</span><span> = </span><span class="func">str_split</span><span>(</span><span class="vars">$key</span><span>); </span></span></li>
<li><span>            <span class="vars">$this</span><span>->arc[] = </span><span class="keyword">new</span><span> EdgeArc(</span><span class="vars">$key</span><span>[0], </span><span class="vars">$key</span><span>[1], </span><span class="vars">$value</span><span>); </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="comment">//对边数组按权值排序</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> sortArc(){ </span></span></li>
<li><span>        <span class="vars">$this</span><span>->quicklySort(0, </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->arc) - 1, </span><span class="vars">$this</span><span>->arc);  </span></span></li>
<li class="alt"><span>        <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->arc;  </span></span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="comment">//采用快排</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> quicklySort(</span><span class="vars">$begin</span><span>, </span><span class="vars">$end</span><span>, & </span><span class="vars">$item</span><span>){ </span></span></li>
<li><span>        <span class="keyword">if</span><span>(</span><span class="vars">$begin</span><span> <span class="vars">$begin</span><span> >= </span><span class="vars">$end</span><span>)) </span></span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span>; </span></span></li>
<li><span>         </span></li>
<li class="alt"><span>        <span class="vars">$key</span><span> = </span><span class="vars">$this</span><span>->excuteSort(</span><span class="vars">$begin</span><span>, </span><span class="vars">$end</span><span>, </span><span class="vars">$item</span><span>); </span></span></li>
<li><span>        <span class="vars">$this</span><span>->quicklySort(0, </span><span class="vars">$key</span><span> - 1, </span><span class="vars">$item</span><span>);  </span></span></li>
<li class="alt"><span>        <span class="vars">$this</span><span>->quicklySort(</span><span class="vars">$key</span><span> + 1, </span><span class="vars">$end</span><span>, </span><span class="vars">$item</span><span>); </span></span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> excuteSort(</span><span class="vars">$begin</span><span>, </span><span class="vars">$end</span><span>, & </span><span class="vars">$item</span><span>){ </span></span></li>
<li class="alt"><span>        <span class="vars">$key</span><span> = </span><span class="vars">$item</span><span>[</span><span class="vars">$begin</span><span>]; </span></span></li>
<li><span>        <span class="vars">$left</span><span> = </span><span class="keyword">array</span><span>(); </span></span></li>
<li class="alt"><span>        <span class="vars">$right</span><span> = </span><span class="keyword">array</span><span>(); </span></span></li>
<li><span>          </span></li>
<li class="alt"><span>        <span class="keyword">for</span><span>(</span><span class="vars">$i</span><span> = (</span><span class="vars">$begin</span><span> + 1); </span><span class="vars">$i</span><span> <span class="vars">$end</span><span>; </span><span class="vars">$i</span><span> ++){ </span></span></span></li>
<li><span>            <span class="keyword">if</span><span>(</span><span class="vars">$item</span><span>[</span><span class="vars">$i</span><span>]->getWeight() <span class="vars">$key</span><span>->getWeight()){ </span></span></span></li>
<li class="alt"><span>                <span class="vars">$left</span><span>[] = </span><span class="vars">$item</span><span>[</span><span class="vars">$i</span><span>];    </span></span></li>
<li><span>            }<span class="keyword">else</span><span>{ </span></span></li>
<li class="alt"><span>                <span class="vars">$right</span><span>[] = </span><span class="vars">$item</span><span>[</span><span class="vars">$i</span><span>]; </span></span></li>
<li><span>            } </span></li>
<li class="alt"><span>        } </span></li>
<li><span>         </span></li>
<li class="alt"><span>        <span class="vars">$return</span><span> = </span><span class="vars">$this</span><span>->unio(</span><span class="vars">$left</span><span>, </span><span class="vars">$right</span><span>, </span><span class="vars">$key</span><span>); </span></span></li>
<li><span>         </span></li>
<li class="alt"><span>        <span class="vars">$k</span><span> = 0; </span></span></li>
<li><span>        <span class="keyword">for</span><span>(</span><span class="vars">$i</span><span> = </span><span class="vars">$begin</span><span>; </span><span class="vars">$i</span><span> <span class="vars">$end</span><span>; </span><span class="vars">$i</span><span> ++){ </span></span></span></li>
<li class="alt"><span>            <span class="vars">$item</span><span>[</span><span class="vars">$i</span><span>] = </span><span class="vars">$return</span><span>[</span><span class="vars">$k</span><span>]; </span></span></li>
<li><span>            <span class="vars">$k</span><span> ++; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">return</span><span> </span><span class="vars">$begin</span><span> + </span><span class="func">count</span><span>(</span><span class="vars">$left</span><span>); </span></span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> unio(</span><span class="vars">$left</span><span>, </span><span class="vars">$right</span><span>, </span><span class="vars">$key</span><span>){ </span></span></li>
<li class="alt"><span>        <span class="keyword">return</span><span> </span><span class="func">array_merge</span><span>(</span><span class="vars">$left</span><span>, </span><span class="keyword">array</span><span>(</span><span class="vars">$key</span><span>), </span><span class="vars">$right</span><span>); </span></span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="comment">//kruscal算法</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> kruscal(){ </span></span></li>
<li><span>        <span class="vars">$this</span><span>->krus = </span><span class="keyword">array</span><span>(); </span></span></li>
<li class="alt"><span>        <span class="vars">$this</span><span>->sortArc(); </span></span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->vexs </span><span class="keyword">as</span><span> </span><span class="vars">$value</span><span>){ </span></span></li>
<li><span>            <span class="vars">$this</span><span>->krus[</span><span class="vars">$value</span><span>] = </span><span class="string">"0"</span><span>; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->arc </span><span class="keyword">as</span><span> </span><span class="vars">$key</span><span>=></span><span class="vars">$value</span><span>){ </span></span></li>
<li><span>            <span class="vars">$begin</span><span> = </span><span class="vars">$this</span><span>->findRoot(</span><span class="vars">$value</span><span>->getBegin()); </span></span></li>
<li class="alt"><span>            <span class="vars">$end</span><span> = </span><span class="vars">$this</span><span>->findRoot(</span><span class="vars">$value</span><span>->getEnd()); </span></span></li>
<li><span>             </span></li>
<li class="alt"><span>            <span class="keyword">if</span><span>(</span><span class="vars">$begin</span><span> != </span><span class="vars">$end</span><span>){ </span></span></li>
<li><span>                <span class="vars">$this</span><span>->krus[</span><span class="vars">$begin</span><span>] = </span><span class="vars">$end</span><span>; </span></span></li>
<li class="alt"><span>                <span class="func">echo</span><span> </span><span class="vars">$value</span><span>->getBegin() . </span><span class="string">"-"</span><span> . </span><span class="vars">$value</span><span>->getEnd() . </span><span class="string">":"</span><span> . </span><span class="vars">$value</span><span>->getWeight() . </span><span class="string">"\n"</span><span>; </span></span></li>
<li><span>            } </span></li>
<li class="alt"><span>        } </span></li>
<li><span>    } </span></li>
<li class="alt"><span> </span></li>
<li><span>    <span class="comment">//查找子树的尾结点</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> findRoot(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span>        <span class="keyword">while</span><span>(</span><span class="vars">$this</span><span>->krus[</span><span class="vars">$node</span><span>] != </span><span class="string">"0"</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$node</span><span> = </span><span class="vars">$this</span><span>->krus[</span><span class="vars">$node</span><span>]; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>         </span></li>
<li><span>        <span class="keyword">return</span><span> </span><span class="vars">$node</span><span>; </span></span></li>
<li class="alt"><span>    } </span></li>
<li><span>} </span></li>
<li class="alt"><span>?> </span></li>
</ol>