<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>
声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
AI Hentai Generator
AIヘンタイを無料で生成します。
人気の記事
R.E.P.O.説明されたエネルギー結晶と彼らが何をするか（黄色のクリスタル）
4週間前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最高のグラフィック設定
4週間前By尊渡假赌尊渡假赌尊渡假赌
アサシンのクリードシャドウズ：シーシェルリドルソリューション
2週間前ByDDD
R.E.P.O.誰も聞こえない場合はオーディオを修正する方法
4週間前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25：Myriseのすべてのロックを解除する方法
1 か月前By尊渡假赌尊渡假赌尊渡假赌
ホットツール
ドリームウィーバー CS6
ビジュアル Web 開発ツール
Safe Exam Browser
Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。
SublimeText3 Linux 新バージョン
SublimeText3 Linux 最新バージョン
MantisBT
Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。
WebStorm Mac版
便利なJavaScript開発ツール
