search
Homephp教程php手册关键路径: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



Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

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

Hot Tools

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

Safe Exam Browser

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.

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools