本文实例讲述了PHP实现图的邻接矩阵表示及几种简单遍历算法。分享给大家供大家参考,具体如下:
这次给大家准备了一些PHP实现图的邻接矩阵表示及几种简单遍历算法。帮助大家在PHP的路上越走越远,一起来看一下。
在web开发中图这种数据结构的应用比树要少很多,但在一些业务中也常有出现,下面介绍几种图的寻径算法,并用PHP加以实现.
佛洛依德算法,主要是在顶点集内,按点与点相邻边的权重做遍历,如果两点不相连则权重无穷大,这样通过多次遍历可以得到点到点的最短路径,逻辑上最好理解,实现也较为简单,时间复杂度为O(n^3);
迪杰斯特拉算法,OSPF中实现最短路由所用到的经典算法,djisktra算法的本质是贪心算法,不断的遍历扩充顶点路径集合S,一旦发现更短的点到点路径就替换S中原有的最短路径,完成所有遍历后S便是所有顶点的最短路径集合了.迪杰斯特拉算法的时间复杂度为O(n^2);
克鲁斯卡尔算法,在图内构造最小生成树,达到图中所有顶点联通.从而得到最短路径.时间复杂度为O(N*logN);
<?php /** * PHP 实现图邻接矩阵 */ class MGraph{ private $vexs; //顶点数组 private $arc; //边邻接矩阵,即二维数组 private $arcData; //边的数组信息 private $direct; //图的类型(无向或有向) private $hasList; //尝试遍历时存储遍历过的结点 private $queue; //广度优先遍历时存储孩子结点的队列,用数组模仿 private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值 private $primVexs; //prim算法时保存顶点 private $primArc; //prim算法时保存边 private $krus;//kruscal算法时保存边的信息 public function MGraph($vexs, $arc, $direct = 0){ $this->vexs = $vexs; $this->arcData = $arc; $this->direct = $direct; $this->initalizeArc(); $this->createArc(); } private function initalizeArc(){ foreach($this->vexs as $value){ foreach($this->vexs as $cValue){ $this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity); } } } //创建图 $direct:0表示无向图,1表示有向图 private function createArc(){ foreach($this->arcData as $key=>$value){ $strArr = str_split($key); $first = $strArr[0]; $last = $strArr[1]; $this->arc[$first][$last] = $value; if(!$this->direct){ $this->arc[$last][$first] = $value; } } } //floyd算法 public function floyd(){ $path = array();//路径数组 $distance = array();//距离数组 foreach($this->arc as $key=>$value){ foreach($value as $k=>$v){ $path[$key][$k] = $k; $distance[$key][$k] = $v; } } for($j = 0; $j < count($this->vexs); $j ++){ for($i = 0; $i < count($this->vexs); $i ++){ for($k = 0; $k < count($this->vexs); $k ++){ if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){ $path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]]; $distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]; } } } } return array($path, $distance); } //djikstra算法 public function dijkstra(){ $final = array(); $pre = array();//要查找的结点的前一个结点数组 $weight = array();//权值和数组 foreach($this->arc[$this->vexs[0]] as $k=>$v){ $final[$k] = 0; $pre[$k] = $this->vexs[0]; $weight[$k] = $v; } $final[$this->vexs[0]] = 1; for($i = 0; $i < count($this->vexs); $i ++){ $key = 0; $min = $this->infinity; for($j = 1; $j < count($this->vexs); $j ++){ $temp = $this->vexs[$j]; if($final[$temp] != 1 && $weight[$temp] < $min){ $key = $temp; $min = $weight[$temp]; } } $final[$key] = 1; for($j = 0; $j < count($this->vexs); $j ++){ $temp = $this->vexs[$j]; if($final[$temp] != 1 && ($min + $this->arc[$key][$temp]) < $weight[$temp]){ $pre[$temp] = $key; $weight[$temp] = $min + $this->arc[$key][$temp]; } } } return $pre; } //kruscal算法 private function kruscal(){ $this->krus = array(); foreach($this->vexs as $value){ $krus[$value] = 0; } foreach($this->arc as $key=>$value){ $begin = $this->findRoot($key); foreach($value as $k=>$v){ $end = $this->findRoot($k); if($begin != $end){ $this->krus[$begin] = $end; } } } } //查找子树的尾结点 private function findRoot($node){ while($this->krus[$node] > 0){ $node = $this->krus[$node]; } return $node; } //prim算法,生成最小生成树 public function prim(){ $this->primVexs = array(); $this->primArc = array($this->vexs[0]=>0); for($i = 1; $i < count($this->vexs); $i ++){ $this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]]; $this->primVexs[$this->vexs[$i]] = $this->vexs[0]; } for($i = 0; $i < count($this->vexs); $i ++){ $min = $this->infinity; $key; foreach($this->vexs as $k=>$v){ if($this->primArc[$v] != 0 && $this->primArc[$v] < $min){ $key = $v; $min = $this->primArc[$v]; } } $this->primArc[$key] = 0; foreach($this->arc[$key] as $k=>$v){ if($this->primArc[$k] != 0 && $v < $this->primArc[$k]){ $this->primArc[$k] = $v; $this->primVexs[$k] = $key; } } } return $this->primVexs; } //一般算法,生成最小生成树 public function bst(){ $this->primVexs = array($this->vexs[0]); $this->primArc = array(); next($this->arc[key($this->arc)]); $key = NULL; $current = NULL; while(count($this->primVexs) < count($this->vexs)){ foreach($this->primVexs as $value){ foreach($this->arc[$value] as $k=>$v){ if(!in_array($k, $this->primVexs) && $v != 0 && $v != $this->infinity){ if($key == NULL || $v < current($current)){ $key = $k; $current = array($value . $k=>$v); } } } } $this->primVexs[] = $key; $this->primArc[key($current)] = current($current); $key = NULL; $current = NULL; } return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc); } //一般遍历 public function reserve(){ $this->hasList = array(); foreach($this->arc as $key=>$value){ if(!in_array($key, $this->hasList)){ $this->hasList[] = $key; } foreach($value as $k=>$v){ if($v == 1 && !in_array($k, $this->hasList)){ $this->hasList[] = $k; } } } foreach($this->vexs as $v){ if(!in_array($v, $this->hasList)) $this->hasList[] = $v; } return implode($this->hasList); } //广度优先遍历 public function bfs(){ $this->hasList = array(); $this->queue = array(); foreach($this->arc as $key=>$value){ if(!in_array($key, $this->hasList)){ $this->hasList[] = $key; $this->queue[] = $value; while(!empty($this->queue)){ $child = array_shift($this->queue); foreach($child as $k=>$v){ if($v == 1 && !in_array($k, $this->hasList)){ $this->hasList[] = $k; $this->queue[] = $this->arc[$k]; } } } } } return implode($this->hasList); } //执行深度优先遍历 public function excuteDfs($key){ $this->hasList[] = $key; foreach($this->arc[$key] as $k=>$v){ if($v == 1 && !in_array($k, $this->hasList)) $this->excuteDfs($k); } } //深度优先遍历 public function dfs(){ $this->hasList = array(); foreach($this->vexs as $key){ if(!in_array($key, $this->hasList)) $this->excuteDfs($key); } return implode($this->hasList); } //返回图的二维数组表示 public function getArc(){ return $this->arc; } //返回结点个数 public function getVexCount(){ return count($this->vexs); } } $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'); $b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');//键为边,值权值 $test = new MGraph($a, $b); print_r($test->bst());
行结果:
Array ( [vexs] => Array ( [0] => a [1] => b [2] => f [3] => i [4] => c [5] => g [6] => h [7] => e [8] => d ) [arc] => Array ( [ab] => 10 [af] => 11 [bi] => 12 [ic] => 8 [bg] => 16 [gh] => 19 [he] => 7 [hd] => 16 ) )
相信看了这些案例你已经掌握了方法,更多精彩请关注php中文网其它相关文章!
相关阅读:
二叉树的非递归后序遍历算法实例详解_javascript技巧
以上是PHP遍历算法的总结的详细内容。更多信息请关注PHP中文网其他相关文章!

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\ \;||\xc2\xa0)/","其他字符",$str)”语句。

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

SublimeText3汉化版
中文版,非常好用