PHP网站制作之邻接矩阵prim:php完成图的邻接矩阵及普...

把例子全部敲进去试验，完成一遍以后就会有心得了，因为你会发现为啥我的程序和书上的一模一样就是结果不正确。新手学习的时候必须承认，不容易，因为我也是过来人，你会发现原来有那么多常用的语句，函数都要记。   
<?php
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
/**
* 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 < 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); 本文链接http://www.cxybl.com/html/wlbc/Php/20120607/28507.html应该大致熟悉了一些学习过程，也许我的过程和你的有些出路，但是不管怎么样是殊途同归，我写这么多，也只是给大家一个借鉴的机会，至于好与不好，默默不敢打包票^0^