PHP实现图的邻接表

<ol class="dp-c">
<li class="alt"><span><span><?php  </span></span></span></li>
<li><span>    <span class="comment">//调用</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">require</span><span> </span><span class="string">'alGraph.php'</span><span>; </span></span></li>
<li><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 class="string">'j'</span><span>); </span></span></li>
<li class="alt"><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">'bc'</span><span>, </span><span class="string">'be'</span><span>, </span><span class="string">'cd'</span><span>, </span><span class="string">'df'</span><span>, </span><span class="string">'fg'</span><span>, </span><span class="string">'gh'</span><span>, </span><span class="string">'ga'</span><span>, </span><span class="string">'hj'</span><span>, </span><span class="string">'gi'</span><span>); </span></span></li>
<li><span> </span></li>
<li class="alt"><span>    <span class="vars">$test</span><span> = </span><span class="keyword">new</span><span> ALGraph(</span><span class="vars">$a</span><span>, </span><span class="vars">$b</span><span>); </span></span></li>
<li><span>    print_r(<span class="vars">$test</span><span>->bfs()); </span></span></li>
<li class="alt"><span>?> </span></li>
<li><span>alGraph.php </span></li>
<li class="alt"><span><?php  </span></span></li>
<li><span>    <span class="comment">//顶点类</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">class</span><span> Vex{ </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$data</span><span>; </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$headLink</span><span>; </span></span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> Vex(</span><span class="vars">$data</span><span>, </span><span class="vars">$headLink</span><span> = NULL){ </span></span></li>
<li><span>            <span class="vars">$this</span><span>->data = </span><span class="vars">$data</span><span>; </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->headLink = </span><span class="vars">$headLink</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> getData(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->data; </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> getHeadLink(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->headLink; </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> setHeadLink(& </span><span class="vars">$link</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->headLink = </span><span class="vars">$link</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="comment">//边类</span><span> </span></span></li>
<li><span>    <span class="keyword">class</span><span> Arc{ </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$key</span><span>; </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$next</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> Arc(</span><span class="vars">$key</span><span>, </span><span class="vars">$next</span><span> = NULL){ </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->key= </span><span class="vars">$key</span><span>; </span></span></li>
<li><span>            <span class="vars">$this</span><span>->next = </span><span class="vars">$next</span><span>;  </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getKey(){ </span></span></li>
<li><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->key; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getNext(){ </span></span></li>
<li><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->next; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setNext(</span><span class="vars">$next</span><span>){ </span></span></li>
<li><span>            <span class="vars">$this</span><span>->next = </span><span class="vars">$next</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">class</span><span> ALGraph{ </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$vexsData</span><span>; </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$vexs</span><span>; </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$arcData</span><span>; </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$excuteDfsResult</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></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> ALGraph(</span><span class="vars">$vexsData</span><span>, </span><span class="vars">$arcData</span><span>){ </span></span></li>
<li><span>            <span class="vars">$this</span><span>->vexsData = </span><span class="vars">$vexsData</span><span>; </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->arcData = </span><span class="vars">$arcData</span><span>; </span></span></li>
<li><span> </span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->createHeadList(); </span></span></li>
<li><span>            <span class="vars">$this</span><span>->createArc();  </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">private</span><span> </span><span class="keyword">function</span><span> createHeadList(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->vexsData </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>->vexs[] = </span><span class="keyword">new</span><span> Vex(</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">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">$value</span><span>){ </span></span></li>
<li class="alt"><span>                <span class="vars">$str</span><span> = </span><span class="func">str_split</span><span>(</span><span class="vars">$value</span><span>); </span></span></li>
<li><span>                 </span></li>
<li class="alt"><span>                <span class="vars">$this</span><span>->createConnect(</span><span class="vars">$str</span><span>[0], </span><span class="vars">$str</span><span>[1]); </span></span></li>
<li><span>                <span class="vars">$this</span><span>->createConnect(</span><span class="vars">$str</span><span>[1], </span><span class="vars">$str</span><span>[0]); </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> createConnect(</span><span class="vars">$first</span><span>, </span><span class="vars">$last</span><span>){ </span></span></li>
<li><span>            <span class="vars">$firstNode</span><span> = & </span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$this</span><span>->getVexByValue(</span><span class="vars">$first</span><span>)]; </span></span></li>
<li class="alt"><span>            <span class="vars">$lastNode</span><span> = </span><span class="keyword">new</span><span> Arc(</span><span class="vars">$this</span><span>->getVexByValue(</span><span class="vars">$last</span><span>)); </span></span></li>
<li><span> </span></li>
<li class="alt"><span>            <span class="vars">$lastNode</span><span>->setNext(</span><span class="vars">$firstNode</span><span>->getHeadLink()); </span></span></li>
<li><span>            <span class="vars">$firstNode</span><span>->setHeadLink(& </span><span class="vars">$lastNode</span><span>); </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">private</span><span> </span><span class="keyword">function</span><span> getVexByValue(</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>->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><span>                <span class="keyword">if</span><span>(</span><span class="vars">$v</span><span>->getData() == </span><span class="vars">$value</span><span>){ </span></span></li>
<li class="alt"><span>                    <span class="keyword">return</span><span> </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 class="comment">//广度优先遍历</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> bfs(){ </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 class="vars">$this</span><span>->queue = </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>->vexs </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">$value</span><span>->getData(), </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">$value</span><span>->getData(); </span></span></li>
<li><span>                    <span class="vars">$this</span><span>->queue[] = </span><span class="vars">$value</span><span>->getHeadLink(); </span></span></li>
<li class="alt"><span>                      </span></li>
<li><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 class="alt"><span>                        <span class="vars">$node</span><span> = </span><span class="func">array_shift</span><span>(</span><span class="vars">$this</span><span>->queue); </span></span></li>
<li><span>                         </span></li>
<li class="alt"><span>                        <span class="keyword">while</span><span>(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span>                            <span class="keyword">if</span><span>(!in_array(</span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$node</span><span>->getKey()]->getData(), </span><span class="vars">$this</span><span>->hasList)){ </span></span></li>
<li class="alt"><span>                                <span class="vars">$info</span><span> = </span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$node</span><span>->getKey()]; </span></span></li>
<li><span>                                <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$info</span><span>->getData(); </span></span></li>
<li class="alt"><span>                                <span class="vars">$this</span><span>->queue[] = </span><span class="vars">$info</span><span>->getHeadLink(); </span></span></li>
<li><span>                            } </span></li>
<li class="alt"><span> </span></li>
<li><span>                            <span class="vars">$node</span><span> = </span><span class="vars">$node</span><span>->getNext();  </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 class="comment">//深度优先遍历入口</span><span> </span></span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> dfs(){ </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>->vexs </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 class="vars">$this</span><span>->excuteDfs(</span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$key</span><span>]->getHeadLink()); </span></span></li>
<li class="alt"><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">$this</span><span>->hasList </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">$this</span><span>->hasList[</span><span class="vars">$key</span><span>] = </span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$value</span><span>]->getData();    </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">private</span><span> </span><span class="keyword">function</span><span> excuteDfs(</span><span class="vars">$arc</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="keyword">if</span><span>(!</span><span class="vars">$arc</span><span>  in_array(</span><span class="vars">$arc</span><span>->getKey(), </span><span class="vars">$this</span><span>->hasList)){ </span></span></li>
<li><span>                <span class="keyword">return</span><span> false;    </span></span></li>
<li class="alt"><span>            } </span></li>
<li><span> </span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->hasList[] = </span><span class="vars">$arc</span><span>->getKey(); </span></span></li>
<li><span>            <span class="vars">$next</span><span> = </span><span class="vars">$this</span><span>->vexs[</span><span class="vars">$arc</span><span>->getKey()]->getHeadLink(); </span></span></li>
<li class="alt"><span>         </span></li>
<li><span>            <span class="keyword">while</span><span>(</span><span class="vars">$next</span><span>){   </span></span></li>
<li class="alt"><span>                <span class="vars">$this</span><span>->excuteDfs(</span><span class="vars">$next</span><span>); </span></span></li>
<li><span>                <span class="vars">$next</span><span> = </span><span class="vars">$next</span><span>->getNext(); </span></span></li>
<li class="alt"><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> getVexs(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</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>