PHP遍历算法的总结

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP遍历算法的总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7037字，纯文字阅读大概需要11分钟。

内容图文

本文实例讲述了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
    )
)

相信看了这些案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！

内容总结

以上是互联网集市为您收集整理的PHP遍历算法的总结全部内容，希望文章能够帮你解决PHP遍历算法的总结所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/140709.html

来源：【匿名】

【上一篇】详解PHP字符串匹配算法【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【PHP遍历算法的总结】教程文章相关的互联网学习教程文章

一.思维导图二.概念笔记树的存储结构双亲表示法:当算法中需要在树结构中频繁地查找某结点的父结点时，使用双亲表示法最合适孩子表示法:适用于查找某结点的孩子结点孩子兄弟表示法:可以用孩子兄弟表示法将普通树转化为二叉树二叉树的性质性质一: 在二叉树的第k层上最多有2^(k-1)个结点性质二: 高度为k的二叉树至多有2^k-1个结点，最少有k个结点性质三: 对任何一棵二叉树T,如果其终端结点数为n0，度为2的结点数为n2,则n0 = n2 + ...

十大经典排序算法总结【代码】【图】

0、排序算法说明0.1 排序的定义对一序列对象根据某个关键字进行排序。0.2 术语说明稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：一个算法执行所耗费的时间。空间复杂度：运行完一个程序所需内存的大小。0....

Memcached 笔记与总结（6）PHP 实现 Memcached 的一致性哈希分布算法【代码】

首先创建一个接口，有 3 个方法：addServer：添加一个服务器到服务器列表中removeServer：从服务器列表中移除一个服务器lookup：在当前的服务器列表中找到合适的服务器存放数据interface distribute{//在当前的服务器列表中找到合适的服务器存放数据publicfunction lookup($key);//添加一个服务器到服务器列表中publicfunction addServer($server);//从服务器列表中删除一个服务器publicfunction removeServer($server); } 再定义一...

查找算法总结(一)—顺序、二分、二叉、红黑【图】

1.顺序查找在查找中我们一个一个顺序的遍历表中的所有键并使用equals（）方法来查找匹配的键。优点：对数组的结构没有特定的要求，可以使用数组或者链表实现，算法简单。缺点：当数组个数n较大时，效率低下。时间复杂度：查找命中时，最大时间复杂度是O(n)，最小时间复杂度是O(1),平均时间复杂度是O(n/2)；未命中时，总需要O(n)次比较。　　　　　　向一个空表中插入N个不同的件需要N2次比较。 2.基于有序数组的二分查找在查找时，...

PHP排序算法的复习和总结【代码】

对于PHP中对数组的元素进行排序，这个是很经常用到的，之前的项目中也有，而且对于几种排序我们都是用的是asort arsort 等PHP原生函数，没有自己去实现，所以就对一下的几个函数进行总结，这个会不断的进行补充，自己也可以好好的复习和总结。直接上代码吧！ 1 <?php2/* 3 * 插入排序（一维数组）4 * 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当的位置，使数列依然有序；直到待排序的数据元素全部插入完成...

分治算法小总结 x【代码】

其实这个题用冒泡排序做的，但用归并排序也能做出来（分析一下此题与逆序对是有相同之处的）由于两者的代码完全一样，就只放一个啦 ~\(≧▽≦)/~啦啦啦1.洛谷 P1116 车厢重组题目描述在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢...

大数据时代：基于微软案例数据库数据挖掘知识点总结（Microsoft 顺序分析和聚类分析算法）【图】

原文:（原创）大数据时代：基于微软案例数据库数据挖掘知识点总结（Microsoft 顺序分析和聚类分析算法）前言本篇文章继续我们的微软挖掘系列算法总结，前几篇文章已经将相关的主要算法做了详细的介绍，我为了展示方便，特地的整理了一个目录提纲篇：大数据时代：深入浅出微软数据挖掘算法总结连载，有兴趣的童鞋可以点击查阅，本篇我们将要总结的算法为：Microsoft顺序分析和聚类分析算法，此算法为上一篇中的关联规则分析算法的一...

几种常见模式识别算法整理和总结

这学期选了门模式识别的课。发现最常见的一种情况就是，书上写的老师ppt上写的都看不懂，然后绕了一大圈去自己查资料理解，回头看看发现，Ah-ha，原来本质的原理那么简单，自己一開始仅仅只是被那些看似formidable的细节吓到了。所以在这里把自己所学的一些点记录下来，供备忘，也供參考。 1. K-Nearest NeighborK-NN能够说是一种最直接的用来分类未知数据的方法。基本通过以下这张图跟文字说明就能够明确K-NN是干什么的简单来说...

paxos算法学习总结【图】

核心思想分布式系统架构下如何让整体尽快达成一致观点，也就是多个不同观点收敛到一个观点的过程。难点可能会发生少数节点故障，但绝不是大面积故障，不然系统也没法正常工作。由于存在单点故障，因此不可能将观点由某一台机器的统一。共享内存达到一致性的方案不可取。因此，只能是点对点通信。一些概念算法中有三个角色Proposor，Acceptor，Learner算法有两个阶段，一是预提案，二是正式提案。正式提案的内容也就是观点，预提案不...

C++算法之——常用算法总结

http://blog.sina.com.cn/s/blog_61bebe480100v7c7.html 基本的C++算法分为三类：排序算法、树算法、图算法算法思想有三种：递推、分治、动态规划以及贪心算法。本文将简要介绍上面三类算法，介绍时穿插介绍算法思想。一、排序算法 1、基本O(n^2)排序算法：（对基本排序算法的时间复杂度分析主要考虑比较次数、数据交换次数）冒泡排序：针对数组、本地排序、需要交换数据。O(1)额外空间选择排序：一般针对数组、本地排序、需...

回溯算法的一个总结【图】

回溯算法的模板：result = [] def backtrack(路径, 选择列表): ????if 满足结束条件:{ ????????result.add(路径) ????????return ? ? }?? ? //每个for代表的其实就是一位，由这个for引出的下一个backtrack就是这位的下一位????for 选择 in 选择列表:{ ????????做选择????????backtrack(路径, 选择列表) ????????撤销选择? ? }?问题一：子集给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能...

基于C语言的算法总结(不定时更新)【代码】

这篇博客我准备写一些我见过的算法，虽然现在我见过的还很少，但我相信会越来越多，方便日后自己查阅好了开始了求解最大子序列和的最有效的算法 1int MaxSubsequenceSum(constint A[], int N)2{3int ThisSum, MaxSum, j;4// 定义本次循环的和与最大和为0 5 ThisSum = MaxSum = 0; 6// 循环求和 7for (j = 0; j < N; j++)8 {9 ThisSum += A[j]; 10// 判断本次的和与最大和的大小，如果本次和比最大和大，把本次和的值...

排序算法总结【代码】

本文将给出六大经典排序的实现。简单排序算法：冒泡，插入，选择改进排序算法：快排，归并，堆排以下排序用到的交换函数：void swap(int &A, int &B) {int temp = A; A = B; B = temp; }1. 冒泡排序2个相邻的元素相互比较，不满足顺序则交换；每遍历一次数组，使一个元素处于最终位置。时间复杂度O(n2)/**/ 空间复杂度O(1)/**/void BubbleSort(int nums[], intleft, intright) {if (nums == NULL || right-left+1 <= 0)retur...

排序算法总结：一、基数排序【代码】

基数排序(Radix sort)是一种非比较型的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序也分为LSD（Least significant digital）和MSD（Most significant digital）两种方式，LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。以LSD为例，假设原来有一串数值如下所示：　　73, 22, 93, 43, 55, 14, 28, 65, 39, 81　　首先根据个位数的数值，在走访数值时将它们分配至编...

机器学习算法总结（二）

SVM上：这个算法应该是机器学习这门课里最重要的部分了。首先是SVM的思想：找到超平面，将两类中距离最近的点分的越开越好（直至二者相等）。然后是函数间隔和几何间隔的定义，二者之间的区别。接着是超平面模型的建立，看看它是如何将问题转化为凸优化问题的。 SVM第一个难点：拉格朗日对偶。由KKT条件可知，起作用的约束都在边界上，这个会用来解释支持向量。由KKT条件知，在S...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / PHP遍历算法的总结

PHP遍历算法的总结

内容导读

内容图文

内容总结

内容备注

内容手机端

【PHP遍历算法的总结】教程文章相关的互联网学习教程文章

树，二叉树和算法总结【代码】【图】

十大经典排序算法总结【代码】【图】

Memcached 笔记与总结（6）PHP 实现 Memcached 的一致性哈希分布算法【代码】

查找算法总结(一)—顺序、二分、二叉、红黑【图】

PHP排序算法的复习和总结【代码】

分治算法小总结 x【代码】

大数据时代：基于微软案例数据库数据挖掘知识点总结（Microsoft 顺序分析和聚类分析算法）【图】

几种常见模式识别算法整理和总结

paxos算法学习总结【图】

C++算法之——常用算法总结

回溯算法的一个总结【图】

基于C语言的算法总结(不定时更新)【代码】

排序算法总结【代码】

排序算法总结：一、基数排序【代码】

机器学习算法总结（二）

PHP - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程