隣接行列 prim: PHP はグラフの隣接行列と Prim (prim アルゴリズム)、Floyd (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 // 幅優先走査中に子ノードを格納するキュー; array
private $infinity = 65535; // 無限大、つまり 2 つの点の間に接続がないことを表します。この例には重み
private $primvexs がありません。 ; //プリムアルゴリズム中に頂点を保存
private $primarc //プリムアルゴリズム中にエッジを保存
public function mgraph($vexs, $arc, $direct = 0){
$ this->vexs = $vexs;
$this->arcdata = $arc;
$this->direct = $direct;
$this ->initalizearc();
$this->createarc();
}
プライベート関数 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();// 距離 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);{
for($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]] = $パス[$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 アルゴリズム
プライベート関数 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