지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > php教程 > php手册 > PHP实现克鲁斯卡尔算法

PHP实现克鲁斯卡尔算法

WBOY
풀어 주다： 2016-06-21 08:53:03
원래의
1053명이 탐색했습니다.

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>
로그인 후 복사



관련 라벨：
function gt nbsp this
원천：php.cn
이전 기사：PHP原理之内存管理中难懂的几个点 다음 기사：PHP实现图的邻矩阵及普利姆算法(Prim)
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
function_exists()는 사용자 정의 함수를 결정할 수 없습니다. 기능 테스트() {                                                                                ...
에서 2024-04-29 11:01:01
0
2
1429
상위 창에 출력이 없습니다. document.onclick = function(){ window.opener.document.write('나는 자식 창의 출력입니다.');
에서 2024-04-18 23:52:34
0
1
1284
PX가 REM 오류로 자동 변환  <style>html {   글꼴 크기: calc(100vw / 3.75);      }body {    글꼴 크기: 0.16rem;      }&l...
에서 2024-04-16 09:34:16
0
0
4687
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿