• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    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相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

    希望本文所述对大家PHP程序设计有所帮助。

    您可能感兴趣的文章:
    • PHP简单实现二维数组的矩阵转置操作示例
    • PHP使用数组实现矩阵数学运算的方法示例
    • PHP实现蛇形矩阵,回环矩阵及数字螺旋矩阵的方法分析
    • PHP 数组和字符串互相转换实现方法
    • PHP中数组合并的两种方法及区别介绍
    • PHP遍历数组的方法汇总
    • PHP遍历数组的几种方法
    • php数组函数序列之array_keys() - 获取数组键名
    • php获取数组中重复数据的两种方法
    • PHP实现顺时针打印矩阵(螺旋矩阵)的方法示例
    上一篇:PHP+Apache环境中如何隐藏Apache版本
    下一篇:PHP简单实现二维数组的矩阵转置操作示例
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

    PHP实现图的邻接矩阵表示及几种简单遍历算法分析 PHP,实现,图,的,邻接,矩阵,