Community Learn Tools Library Leisure
search
English
Home > php教程 > php手册 > PHP实现克鲁斯卡尔算法

PHP实现克鲁斯卡尔算法

WBOY
Release： 2016-06-21 08:53:03
Original
1053 people have browsed it

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>
Copy after login



Related labels：
function gt nbsp this
source：php.cn
Previous article：PHP原理之内存管理中难懂的几个点 Next article：PHP实现图的邻矩阵及普利姆算法(Prim)
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
function_exists() cannot determine the custom function Function test () {return true;} if (function_exists ('test')) {echo "test is function...
From 2024-04-29 11:01:01
0
2
1429
There is no output in the parent window document.onclick = function(){ window.opener.document.write('I am the output of the child ...
From 2024-04-18 23:52:34
0
1
1284
PX automatic conversion to REM error  <style>html {   font-size: calc(100vw / 3.75);      }...
From 2024-04-16 09:34:16
0
0
4687
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template