搜尋
首頁後端開發php教程PHP遍歷演算法的總結
PHP遍歷演算法的總結Dec 20, 2017 pm 04:29 PM
php總結演算法

本文實例敘述了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(&#39;vexs&#39;=>$this->primVexs, &#39;arc&#39;=>$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(&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;, &#39;f&#39;, &#39;g&#39;, &#39;h&#39;, &#39;i&#39;);
$b = array(&#39;ab&#39;=>&#39;10&#39;, &#39;af&#39;=>&#39;11&#39;, &#39;bg&#39;=>&#39;16&#39;, &#39;fg&#39;=>&#39;17&#39;, &#39;bc&#39;=>&#39;18&#39;, &#39;bi&#39;=>&#39;12&#39;, &#39;ci&#39;=>&#39;8&#39;, &#39;cd&#39;=>&#39;22&#39;, &#39;di&#39;=>&#39;21&#39;, &#39;dg&#39;=>&#39;24&#39;, &#39;gh&#39;=>&#39;19&#39;, &#39;dh&#39;=>&#39;16&#39;, &#39;de&#39;=>&#39;20&#39;, &#39;eh&#39;=>&#39;7&#39;,&#39;fe&#39;=>&#39;26&#39;);//键为边,值权值
$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實作的二元樹遍歷演算法範例程式碼詳解

二元樹的非遞歸後序遍歷演算法實例詳解_javascript技巧

####################################################################################################################### ####

以上是PHP遍歷演算法的總結的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

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

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

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

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

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

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

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

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

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

php怎么判断有没有小数点php怎么判断有没有小数点Apr 20, 2022 pm 08:12 PM

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

php怎么设置implode没有分隔符php怎么设置implode没有分隔符Apr 18, 2022 pm 05:39 PM

在PHP中,可以利用implode()函数的第一个参数来设置没有分隔符,该函数的第一个参数用于规定数组元素之间放置的内容,默认是空字符串,也可将第一个参数设置为空,语法为“implode(数组)”或者“implode("",数组)”。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

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

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!