Gemeinschaft Lernen Tools-Bibliothek Freizeit
suchen
Deutsch
Heim > php教程 > php手册 > PHP实现克鲁斯卡尔算法

PHP实现克鲁斯卡尔算法

WBOY
Freigeben： 2016-06-21 08:53:03
Original
1052 Leute haben es durchsucht

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>
Nach dem Login kopieren



Verwandte Etiketten：
function gt nbsp this
Quelle：php.cn
Vorheriger Artikel：PHP原理之内存管理中难懂的几个点 Nächster Artikel：PHP实现图的邻矩阵及普利姆算法(Prim)
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Aktuelle Ausgaben
function_exists() kann die benutzerdefinierte Funktion nicht ermitteln Funktionstest () {Verwendung der Verwendung durch -Durch -Durch -Durch -Durch -Durch -Durc...
Aus 2024-04-29 11:01:01
0
2
1429
Im übergeordneten Fenster erfolgt keine Ausgabe document.onclick = function(){ window.opener.document.write('Ich bin die Ausgabe des unter...
Aus 2024-04-18 23:52:34
0
1
1284
Automatische PX-Konvertierung in REM-Fehler  <style>html {  font-size: calc(100vw / 3.75);      }body {    Schriftgröße: 0,16rem...
Aus 2024-04-16 09:34:16
0
0
4687
verwandte Themen
Mehr>
Beliebte Empfehlungen
Beliebte Tutorials
Mehr>
Verwandte Tutorials
Beliebte Empfehlungen
Aktuelle Kurse
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage