<ol class="dp-c"><li class="alt"><span><span><?php </span></span></li><li><span> <span class="keyword">require</span><span> </span><span class="string">'mGraph.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">'bg'</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 class="comment">//键为边,值权值</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> MGraph(</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>->prim()); </span></span></li><li><span>?> </span></li><li class="alt"><span><span class="comment">//mGraph.php</span><span> </span></span></li><li><span><?php </span></li><li class="alt"><span> <span class="keyword">class</span><span> MGraph{ </span></span></li><li><span> <span class="keyword">private</span><span> </span><span class="vars">$vexs</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">$arc</span><span>; </span><span class="comment">//边邻接矩阵,即二维数组 </span><span> </span></span></li><li><span> <span class="keyword">private</span><span> </span><span class="vars">$arcData</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">$direct</span><span>; </span><span class="comment">//图的类型(无向或有向)</span><span> </span></span></li><li><span> <span class="keyword">private</span><span> </span><span class="vars">$hasList</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">$queue</span><span>; </span><span class="comment">//广度优先遍历时存储孩子结点的队列,用数组模仿</span><span> </span></span></li><li><span> <span class="keyword">private</span><span> </span><span class="vars">$infinity</span><span> = 65535;</span><span class="comment">//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值 </span><span> </span></span></li><li class="alt"><span> <span class="keyword">private</span><span> </span><span class="vars">$primVexs</span><span>; </span><span class="comment">//prim算法时保存顶点</span><span> </span></span></li><li><span> <span class="keyword">private</span><span> </span><span class="vars">$primArc</span><span>; </span><span class="comment">//prim算法时保存边</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> MGraph(</span><span class="vars">$vexs</span><span>, </span><span class="vars">$arc</span><span>, </span><span class="vars">$direct</span><span> = 0){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->vexs = </span><span class="vars">$vexs</span><span>; </span></span></li><li><span> <span class="vars">$this</span><span>->arcData = </span><span class="vars">$arc</span><span>; </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->direct = </span><span class="vars">$direct</span><span>; </span></span></li><li><span> <span class="vars">$this</span><span>->initalizeArc(); </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="keyword">private</span><span> </span><span class="keyword">function</span><span> initalizeArc(){ </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="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->vexs </span><span class="keyword">as</span><span> </span><span class="vars">$cValue</span><span>){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->arc[</span><span class="vars">$value</span><span>][</span><span class="vars">$cValue</span><span>] = (</span><span class="vars">$value</span><span> == </span><span class="vars">$cValue</span><span> ? 0 : </span><span class="vars">$this</span><span>->infinity); </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">//创建图 $direct:0表示无向图,1表示有向图</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">$strArr</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">$first</span><span> = </span><span class="vars">$strArr</span><span>[0]; </span></span></li><li class="alt"><span> <span class="vars">$last</span><span> = </span><span class="vars">$strArr</span><span>[1]; </span></span></li><li><span> </span></li><li class="alt"><span> <span class="vars">$this</span><span>->arc[</span><span class="vars">$first</span><span>][</span><span class="vars">$last</span><span>] = </span><span class="vars">$value</span><span>; </span></span></li><li><span> <span class="keyword">if</span><span>(!</span><span class="vars">$this</span><span>->direct){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->arc[</span><span class="vars">$last</span><span>][</span><span class="vars">$first</span><span>] = </span><span class="vars">$value</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">//prim算法,生成最小生成树</span><span> </span></span></li><li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> prim(){ </span></span></li><li><span> <span class="vars">$this</span><span>->primVexs = </span><span class="keyword">array</span><span>(); </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->primArc = </span><span class="keyword">array</span><span>(</span><span class="vars">$this</span><span>->vexs[0]=>0); </span></span></li><li><span> </span></li><li class="alt"><span> <span class="keyword">for</span><span>(</span><span class="vars">$i</span><span> = 1; </span><span class="vars">$i</span><span> < </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->vexs); </span><span class="vars">$i</span><span> ++){ </span></span></li><li><span> <span class="vars">$this</span><span>->primArc[</span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$i</span><span>]] = </span><span class="vars">$this</span><span>->arc[</span><span class="vars">$this</span><span>->vexs[0]][</span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$i</span><span>]]; </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->primVexs[</span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$i</span><span>]] = </span><span class="vars">$this</span><span>->vexs[0]; </span></span></li><li><span> } </span></li><li class="alt"><span> </span></li><li><span> <span class="keyword">for</span><span>(</span><span class="vars">$i</span><span> = 0; </span><span class="vars">$i</span><span> < </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->vexs); </span><span class="vars">$i</span><span> ++){ </span></span></li><li class="alt"><span> <span class="vars">$min</span><span> = </span><span class="vars">$this</span><span>->infinity; </span></span></li><li><span> <span class="vars">$key</span><span>; </span></span></li><li class="alt"><span> </span></li><li><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">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$this</span><span>->primArc[</span><span class="vars">$v</span><span>] != 0 && </span><span class="vars">$this</span><span>->primArc[</span><span class="vars">$v</span><span>] < </span><span class="vars">$min</span><span>){ </span></span></li><li><span> <span class="vars">$key</span><span> = </span><span class="vars">$v</span><span>; </span></span></li><li class="alt"><span> <span class="vars">$min</span><span> = </span><span class="vars">$this</span><span>->primArc[</span><span class="vars">$v</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">$this</span><span>->primArc[</span><span class="vars">$key</span><span>] = 0; </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="vars">$key</span><span>] </span><span class="keyword">as</span><span> </span><span class="vars">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li><li><span> <span class="keyword">if</span><span>(</span><span class="vars">$this</span><span>->primArc[</span><span class="vars">$k</span><span>] != 0 && </span><span class="vars">$v</span><span> < </span><span class="vars">$this</span><span>->primArc[</span><span class="vars">$k</span><span>]){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->primArc[</span><span class="vars">$k</span><span>] = </span><span class="vars">$v</span><span>; </span></span></li><li><span> <span class="vars">$this</span><span>->primVexs[</span><span class="vars">$k</span><span>] = </span><span class="vars">$key</span><span>; </span></span></li><li class="alt"><span> } </span></li><li><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">$this</span><span>->primVexs; </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> bst(){ </span></span></li><li><span> <span class="vars">$this</span><span>->primVexs = </span><span class="keyword">array</span><span>(</span><span class="vars">$this</span><span>->vexs[0]); </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->primArc = </span><span class="keyword">array</span><span>(); </span></span></li><li><span> </span></li><li class="alt"><span> next(<span class="vars">$this</span><span>->arc[key(</span><span class="vars">$this</span><span>->arc)]); </span></span></li><li><span> <span class="vars">$key</span><span> = NULL; </span></span></li><li class="alt"><span> <span class="vars">$current</span><span> = NULL; </span></span></li><li><span> </span></li><li class="alt"><span> <span class="keyword">while</span><span>(</span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->primVexs) < </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->vexs)){ </span></span></li><li><span> <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->primVexs </span><span class="keyword">as</span><span> </span><span class="vars">$value</span><span>){ </span></span></li><li class="alt"><span> <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->arc[</span><span class="vars">$value</span><span>] </span><span class="keyword">as</span><span> </span><span class="vars">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li><li><span> <span class="keyword">if</span><span>(!in_array(</span><span class="vars">$k</span><span>, </span><span class="vars">$this</span><span>->primVexs) && </span><span class="vars">$v</span><span> != 0 && </span><span class="vars">$v</span><span> != </span><span class="vars">$this</span><span>->infinity){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$key</span><span> == NULL </span><span class="vars">$v</span><span> < current(</span><span class="vars">$current</span><span>)){ </span></span></li><li><span> <span class="vars">$key</span><span> = </span><span class="vars">$k</span><span>; </span></span></li><li class="alt"><span> <span class="vars">$current</span><span> = </span><span class="keyword">array</span><span>(</span><span class="vars">$value</span><span> . </span><span class="vars">$k</span><span>=></span><span class="vars">$v</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></li><li class="alt"><span> </span></li><li><span> <span class="vars">$this</span><span>->primVexs[] = </span><span class="vars">$key</span><span>; </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->primArc[key(</span><span class="vars">$current</span><span>)] = current(</span><span class="vars">$current</span><span>); </span></span></li><li><span> <span class="vars">$key</span><span> = NULL; </span></span></li><li class="alt"><span> <span class="vars">$current</span><span> = NULL; </span></span></li><li><span> } </span></li><li class="alt"><span> </span></li><li><span> <span class="keyword">return</span><span> </span><span class="keyword">array</span><span>(</span><span class="string">'vexs'</span><span>=></span><span class="vars">$this</span><span>->primVexs, </span><span class="string">'arc'</span><span>=></span><span class="vars">$this</span><span>->primArc); </span></span></li><li class="alt"><span> } </span></li><li><span> </span></li><li class="alt"><span> <span class="comment">//一般遍历</span><span> </span></span></li><li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> reserve(){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->hasList = </span><span class="keyword">array</span><span>(); </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="keyword">if</span><span>(!in_array(</span><span class="vars">$key</span><span>, </span><span class="vars">$this</span><span>->hasList)){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$key</span><span>; </span></span></li><li><span> } </span></li><li class="alt"><span> </span></li><li><span> <span class="keyword">foreach</span><span>(</span><span class="vars">$value</span><span> </span><span class="keyword">as</span><span> </span><span class="vars">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$v</span><span> == 1 && !in_array(</span><span class="vars">$k</span><span>, </span><span class="vars">$this</span><span>->hasList)){ </span></span></li><li><span> <span class="vars">$this</span><span>->hasList[] = </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></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">$v</span><span>){ </span></span></li><li><span> <span class="keyword">if</span><span>(!in_array(</span><span class="vars">$v</span><span>, </span><span class="vars">$this</span><span>->hasList)) </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$v</span><span>; </span></span></li><li><span> } </span></li><li class="alt"><span> </span></li><li><span> <span class="keyword">return</span><span> implode(</span><span class="vars">$this</span><span>->hasList); </span></span></li><li class="alt"><span> } </span></li><li><span> </span></li><li class="alt"><span> <span class="comment">//广度优先遍历</span><span> </span></span></li><li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> bfs(){ </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->hasList = </span><span class="keyword">array</span><span>(); </span></span></li><li><span> <span class="vars">$this</span><span>->queue = </span><span class="keyword">array</span><span>(); </span></span></li><li class="alt"><span> </span></li><li><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 class="alt"><span> <span class="keyword">if</span><span>(!in_array(</span><span class="vars">$key</span><span>, </span><span class="vars">$this</span><span>->hasList)){ </span></span></li><li><span> <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$key</span><span>; </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->queue[] = </span><span class="vars">$value</span><span>; </span></span></li><li><span> </span></li><li class="alt"><span> <span class="keyword">while</span><span>(!</span><span class="func">empty</span><span class="keyword">empty</span><span>(</span><span class="vars">$this</span><span>->queue)){ </span></span></li><li><span> <span class="vars">$child</span><span> = </span><span class="func">array_shift</span><span>(</span><span class="vars">$this</span><span>->queue); </span></span></li><li class="alt"><span> </span></li><li><span> <span class="keyword">foreach</span><span>(</span><span class="vars">$child</span><span> </span><span class="keyword">as</span><span> </span><span class="vars">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$v</span><span> == 1 && !in_array(</span><span class="vars">$k</span><span>, </span><span class="vars">$this</span><span>->hasList)){ </span></span></li><li><span> <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$k</span><span>; </span></span></li><li class="alt"><span> <span class="vars">$this</span><span>->queue[] = </span><span class="vars">$this</span><span>->arc[</span><span class="vars">$k</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></li><li class="alt"><span> </span></li><li><span> <span class="keyword">return</span><span> implode(</span><span class="vars">$this</span><span>->hasList); </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> excuteDfs(</span><span class="vars">$key</span><span>){ </span></span></li><li><span> <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$key</span><span>; </span></span></li><li class="alt"><span> </span></li><li><span> <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->arc[</span><span class="vars">$key</span><span>] </span><span class="keyword">as</span><span> </span><span class="vars">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$v</span><span> == 1 && !in_array(</span><span class="vars">$k</span><span>, </span><span class="vars">$this</span><span>->hasList)) </span></span></li><li><span> <span class="vars">$this</span><span>->excuteDfs(</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></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> dfs(){ </span></span></li><li><span> <span class="vars">$this</span><span>->hasList = </span><span class="keyword">array</span><span>(); </span></span></li><li class="alt"><span> </span></li><li><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">$key</span><span>){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>(!in_array(</span><span class="vars">$key</span><span>, </span><span class="vars">$this</span><span>->hasList)) </span></span></li><li><span> <span class="vars">$this</span><span>->excuteDfs(</span><span class="vars">$key</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> implode(</span><span class="vars">$this</span><span>->hasList); </span></span></li><li><span> } </span></li><li class="alt"><span> <span class="comment">//返回图的二维数组表示</span><span> </span></span></li><li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getArc(){ </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 class="comment">//返回结点个数</span><span> </span></span></li><li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getVexCount(){ </span></span></li><li class="alt"><span> <span class="keyword">return</span><span> </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->vexs); </span></span></li><li><span> } </span></li><li class="alt"><span> } </span></li><li><span>?> </span></li></ol>
