邻接矩阵prim:php实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法

require 'mgraph.php';
$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->prim());
?>
mgraph.php
/**
* php 实现图邻接矩阵
*
* @author zhaojiangwei
* @since 2011/10/31 17:23
*/
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 vexs); $j ++){
for($i = 0; $i vexs); $i ++){
for($k = 0; $k 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 vexs); $i ++){
$key = 0;
$min = $this->infinity;
for($j = 1; $j vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 && $weight[$temp] $key = $temp;
$min = $weight[$temp];
}
}
$final[$key] = 1;
for($j = 0; $j vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 && ($min + $this->arc[$key][$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); 本文链接http://www.cxybl.com/html/wlbc/Php/20120607/28507.html