백엔드 개발 PHP 튜토리얼 PHP 순회 알고리즘 요약

PHP 순회 알고리즘 요약

Dec 20, 2017 pm 04:29 PM
php 요약 연산

이 문서의 예에서는 PHP로 구현된 그래프의 인접 행렬 표현과 몇 가지 간단한 순회 알고리즘을 설명합니다. 참조를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

이번에는 PHP 구현 그래프의 인접 행렬 표현과 몇 가지 간단한 순회 알고리즘을 준비했습니다. 모든 사람이 PHP의 길에서 더욱 더 나아갈 수 있도록 돕기 위해 살펴보겠습니다.

웹 개발에서 그래프와 같은 데이터 구조의 적용은 트리의 적용보다 훨씬 적지만 일부 비즈니스에서는 종종 나타납니다. 아래에 소개되고 PHP로 구현된 몇 가지 그래프 경로 찾기 알고리즘이 있습니다.

Floyd 알고리즘 주로 점 사이의 인접한 모서리의 가중치에 따라 설정된 정점을 통과합니다. 두 점이 연결되어 있지 않으면 가중치는 무한대입니다. 이렇게 하면 여러 번의 순회를 통해 점 간 최단 경로를 얻을 수 있습니다. 논리적으로 이해하기 가장 좋습니다. 구현은 O(n^3)의 시간 복잡도로 비교적 간단합니다.

Dijsktra 알고리즘은 OSPF에서 최단 경로를 구현하는 데 사용되는 알고리즘입니다. 정점 경로를 지속적으로 탐색하고 확장하는 알고리즘입니다. 짧은 지점 간 경로가 발견되면 S의 원래 최단 경로가 모든 탐색을 완료한 후 S가 모든 정점에 대한 최단 경로 집합이 됩니다. . Dijkstra 알고리즘의 시간 복잡도는 O(n ^2)입니다.

Kruskal의 알고리즘은 그래프의 모든 정점을 연결하기 위해 그래프에 최소 신장 트리를 구성합니다. 따라서 시간 복잡도는 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 순회 알고리즘 요약의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Dec 24, 2024 pm 04:42 PM

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드

CakePHP 날짜 및 시간 CakePHP 날짜 및 시간 Sep 10, 2024 pm 05:27 PM

CakePHP 날짜 및 시간

CakePHP 프로젝트 구성 CakePHP 프로젝트 구성 Sep 10, 2024 pm 05:25 PM

CakePHP 프로젝트 구성

CakePHP 파일 업로드 CakePHP 파일 업로드 Sep 10, 2024 pm 05:27 PM

CakePHP 파일 업로드

CakePHP 라우팅 CakePHP 라우팅 Sep 10, 2024 pm 05:25 PM

CakePHP 라우팅

CakePHP 토론 CakePHP 토론 Sep 10, 2024 pm 05:28 PM

CakePHP 토론

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 Dec 20, 2024 am 11:31 AM

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법

CakePHP 빠른 가이드 CakePHP 빠른 가이드 Sep 10, 2024 pm 05:27 PM

CakePHP 빠른 가이드

See all articles