PHPはグラフの隣接リストを実装します
- WBOYオリジナル
- 2016-06-21 08:53:04800ブラウズ
<ol class="dp-c">
<li class="alt"><span><span><?php </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></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>
</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>
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。