Home > Article > Backend Development > Summary of PHP traversal algorithm
Summary of PHP traversal algorithm
- php中世界最好的语言Original
- 2017-12-20 16:29:411569browse
The examples in this article describe the adjacency matrix representation of graphs implemented in PHP and several simple traversal algorithms. Share it with everyone for your reference, the details are as follows:
This time I have prepared some adjacency matrix representations of PHP implementation graphs and several simple traversal algorithms. To help everyone go further and further on the road of PHP, let’s take a look.
In web development, the application of data structures like graphs is much less than that of trees, but it often appears in some businesses. The following introduces several graph path-finding algorithms and uses PHP to implement them.
Freud's algorithm mainly traverses the vertex set according to the weight of the adjacent edges between points. If the two points are not connected, the weight will be infinite. In this way, the shortest point-to-point path can be obtained through multiple traversals. Path is the easiest to understand logically and is relatively simple to implement. The time complexity is O(n^3);
Djisktra algorithm, the classic algorithm used to implement the shortest route in OSPF, djisktra algorithm The essence is a greedy algorithm, which continuously traverses and expands the vertex path set S. Once a shorter point-to-point path is found, the original shortest path in S is replaced. After all traversals are completed, S is the shortest path set of all vertices. Dijie The time complexity of Stella's algorithm is O(n^2);
Kruskal's algorithm constructs a minimum spanning tree in the graph to connect all vertices in the graph. Thus, the shortest path is obtained. The time complexity The degree is 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());Row result:
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
)
)I believe you have mastered the method after reading these cases. For more exciting information, please pay attention to other related articles on the PHP Chinese website!
Related reading:
Binary treeTraversal algorithm-Example of php
binary tree implemented by php Traversal algorithmDetailed explanation of sample code
The above is the detailed content of Summary of PHP traversal algorithm. For more information, please follow other related articles on the PHP Chinese website!