//调用
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

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

SublimeText3 Chinese version
Chinese version, very easy to use

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

SublimeText3 Linux new version
SublimeText3 Linux latest version

SecLists
SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.
