关键路径: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 $haslist; //遍历时储存遍历过的结点下标
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