クリティカル パス: PHP はグラフ隣接リスト、クリティカル パス、トポロジカル ソートを実装します。

//调用
require 'algraph.php';
$a = array('a', 'b', 'c', 'd', 'e' , 'f', 'g', 'h', 'i', 'j');
$e = array('ab'=>'3', 'ac'=>'4', 'be'=>'6'、'bd'=>'5'、'cd'=>'8'、'cf'=>'7'、'de'=>'3'、 'eg'=>'9'、'eh'=>'4'、'fh'=>'6'、'gj'=>'2'、'hi'=>'5'、 'ij'=>'3');
$test = new algraph($a, $e, 1, 1);
print_r($test->criticalpath());
? >
algraph.php
/**
* グラフ隣接リストの PHP 実装
*
* @author zhaojiangwei
* @since 2011/11/1 16:00
*/
//顶点类
class vex{
private $data;
private $headlink;//第一条边
private $enterlimit = 0;//顶点の入度
public function vex($data, $headlink = null){
$this->data = $data;
$this->headlink = $headlink;
}
//入度加+n
public function enterlimitadd($n = 1){
$this-> ;enterlimit += $n;
}
public function getenterlimit(){
return $this->enterlimit;
}
public function getdata(){
return $this ->data;
}
public function getheadlink(){
return $this->headlink;
}
public function setheadlink(& $link){
$this ->headlink = $link;
}
}
//边类
class arc{
private $key;//该边顶点对应在顶量组的下标
private $weight;//路径长度
private $next;//下一条
public function arc($key, $weight = null, $next = null){
$this->; key= $key;
$this->next = $next;
$this->weight= $weight;
}
public function getweight(){
return $this ->weight;
}
public function getkey(){
return $this->key;
}
public function getnext(){
return $this-> ;next;
}
public function setnext($next){
$this->next = $next;
}
}
//邻接表类
class algraph{
private $vexsdata;//外部入力の顶量データ,似たようなarray('a', 'b');
private $vexs;//顶量组
private $arcdata;/ /外部入力のデータデータ、例えばarray('ab'=>'3'),键として边,值として权值
private $excutedfsresult;//深度优先遍历後の文字列结果
private $ハスリスト; //遍在历过的结点下标
private $queue; //广度优先遍历時の存储队列
private $direct; // 有無は有方向、0 は無方向、1 は有方向
private $weight; //否か带权,0不带,1带
//$direct:否か有向图,0無向,1有向
//$weight:否か带权,0不带,1带
public function algraph($vexsdata, $arcdata, $direct = 0, $weight = 0){
$this->vexsdata = $vexsdata;
$this->arcdata = $arcdata ;
$this->direct = $direct;
$this->weight = $weight;
$this->createheadlist();
$this->createarc() ;
}
//创建顶金額组
private function createheadlist(){
foreach($this->vexsdata as $value){
$this->vexs[] = new vex($value);
}
}
//创建边表
private function createarc(){
switch($this->weight){
case ' 0'://不带权
$this->createnoweightarc();
break;
case '1'://带权
$this->createweightarc();
break;
}
}
//创建带权表
private function createweightarc(){
foreach($this->arcdata as $key=>$value) {
$edgenode = str_split($key);
$this->createconnect($edgenode[0], $edgenode[1], $value);
if(!$this-> direct){//有向图
$this->createconnect($edgenode[1], $edgenode[0], $value);
}
}
}
/ /创建不带权表
private function createnoweightarc(){
foreach($this->arcdata as $value){
$str = str_split($value);
$this-> ;createconnect($str[0], $str[1]);
if(!$this->direct){
$this->createconnect($str[1], $str[0] ]);
}
}
}
//边的俩顶点建立关系
//$weight: 权值,默认無权值
private function createconnect ($first, $last, $weight = null){
$lasttemp=& $this->vexs[$this->getvexbyvalue($last)];
$lasttemp->enterlimitadd(1) );//入度+1
$firstnode =& $this->vexs[$this->getvexbyvalue($first)];
$lastnode = new arc($this->getvexbyvalue( $last), $weight);
$lastnode->setnext($firstnode->getheadlink());
$firstnode->setheadlink(& $lastnode); 本文http://www.cxybl.com/html/wlbc/Php/20120607/28508.html