Rumah > Artikel > pembangunan bahagian belakang > PHP实现图的邻接矩阵表示及遍历算法
PHP实现图的邻接矩阵表示及遍历算法
- 墨辰丷asal
- 2018-05-17 10:23:271565semak imbas
这篇文章主要介绍了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
)
)相关推荐：
JavaScript关于多叉树的递归遍历和非递归遍历算法分享
Atas ialah kandungan terperinci PHP实现图的邻接矩阵表示及遍历算法. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Kenyataan：
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel sebelumnya：PHP+Session防止表单重复提交步骤详解Artikel seterusnya：PHP创建Composer包步骤详解
Artikel berkaitan
Lihat lagi- Cara menggunakan cURL untuk melaksanakan permintaan Dapatkan dan Hantar dalam PHP
- Cara menggunakan cURL untuk melaksanakan permintaan Dapatkan dan Hantar dalam PHP
- Cara menggunakan cURL untuk melaksanakan permintaan Dapatkan dan Hantar dalam PHP
- Cara menggunakan cURL untuk melaksanakan permintaan Dapatkan dan Hantar dalam PHP
- Semua simbol ungkapan dalam ungkapan biasa (ringkasan)