- 浏览: 134898 次
- 性别:
- 来自: 北京
文章分类
最新评论
<?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 /** * 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); } //关键路径算法 public function criticalPath(){ $etvs = array();//最早开始时间 $ltvs = array();//最晚开始时间 $stacks = array();//拓朴排序结点栈 $result = array();//返回的结果 foreach($this->vexs as $value){ $etvs[$value->getData()] = 0; } $this->expandSeq($etvs, $stacks);//拓朴排序,并填充$etvs与$stacks $temp = end($etvs);//结点栈的栈顶点,为数组的最后一个元素 foreach($this->vexs as $value){ $ltvs[$value->getData()] = $temp; } while($top = array_pop($stacks)){ $pre = $top->getHeadLink(); while($pre){ $tempNode = $this->vexs[$pre->getKey()]; if($ltvs[$top->getData()] > $ltvs[$tempNode->getData()] - $pre->getWeight()){ $ltvs[$top->getData()] = $ltvs[$tempNode->getData()] - $pre->getWeight(); } $pre = $pre->getNext(); } } foreach($this->vexs as $value){ if($ltvs[$value->getData()] == $etvs[$value->getData()]){ $result[] = $value->getData(); } } return $result; } //拓扑排序 //$etv,关键路径,找最早开始时间,默认为不找 //$stack排序后的顶点栈 public function expandSeq(& $etv = FALSE, & $stacks){ $zeroEnter = array(); $result = array(); foreach($this->vexs as $value){ if($value->getEnterLimit() == 0){ $zeroEnter[] = $value; } } while(!empty($zeroEnter)){ $node = array_shift($zeroEnter); $result[] = $node->getData(); array_push($stacks, $node); $pre = $node->getHeadLink(); while($pre){ $temp =& $this->vexs[$pre->getKey()]; $temp->enterLimitAdd(-1); if($etv){ if($etv[$temp->getData()] < $etv[$node->getData()] + $pre->getWeight()){ $etv[$temp->getData()] = $etv[$node->getData()] + $pre->getWeight(); } } if($temp->getEnterLimit() == 0){ $zeroEnter[] = $temp; } $pre = $pre->getNext(); } } return $result; } //根据顶点的值返回顶点在顶点数组中的下标 private function getVexByValue($value){ foreach($this->vexs as $k=>$v){ if($v->getData() == $value){ return $k; } } } //广度优先遍历 public function bfs(){ $this->hasList = array(); $this->queue = array(); foreach($this->vexs as $key=>$value){ if(!in_array($value->getData(), $this->hasList)){ $this->hasList[] = $value->getData(); $this->queue[] = $value->getHeadLink(); while(!empty($this->queue)){ $node = array_shift($this->queue); while($node){ if(!in_array($this->vexs[$node->getKey()]->getData(), $this->hasList)){ $info = $this->vexs[$node->getKey()]; $this->hasList[] = $info->getData(); $this->queue[] = $info->getHeadLink(); } $node = $node->getNext(); } } } } return implode($this->hasList); } //深度优先遍历入口 public function dfs(){ $this->hasList = array(); foreach($this->vexs as $key=>$value){ if(!in_array($key, $this->hasList)){ $this->hasList[] = $key; $this->excuteDfs($this->vexs[$key]->getHeadLink()); } } foreach($this->hasList as $key=>$value){ $this->hasList[$key] = $this->vexs[$value]->getData(); } return implode($this->hasList); } //执行深度遍历 private function excuteDfs($arc){ if(!$arc || in_array($arc->getKey(), $this->hasList)){ return false; } $this->hasList[] = $arc->getKey(); $next = $this->vexs[$arc->getKey()]->getHeadLink(); while($next){ $this->excuteDfs($next); $next = $next->getNext(); } } public function getVexs(){ return $this->vexs; } } ?>
发表评论
文章已被作者锁定,不允许评论。
-
c实现bitmap
2013-05-14 14:34 1314直接上代码. #include <stdio.h> ... -
nginx hash源码分析
2013-02-05 19:05 1192HASH是NGINX核心数据结构之一.见几个链接.分析的很详细 ... -
贪心算法与动态规划的区别
2012-11-24 21:07 31441.贪心算法和动态规划区别 贪心算法是自顶向下的,它会先做在 ... -
PHP实现各种排序
2011-11-23 17:32 901<?php /** * 各种排序 * @aut ... -
PHP实现平衡二叉树(AVL树)
2011-11-20 17:20 2903<?php require 'bstOrder ... -
PHP实现克鲁斯卡尔(kruscal)算法
2011-11-05 21:18 1150<?php require 'edge.php ... -
PHP实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法
2011-11-02 18:35 4610<?php require 'mGraph.p ... -
PHP实现二叉树,线索二叉树
2011-10-26 19:56 6282<?php require 'biTree ... -
php 实现KMP算法
2011-10-23 12:32 1818<?php /** * KMP算法的P ... -
php实现单链表(静态链表)
2011-10-21 14:40 1788<?php /* * 单链表的PH ...
相关推荐
逆邻接表实现拓扑排序,能够更快速直接的计算顶点的入度,即终点指向结点,有几个边表,则代表入度是几
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
建立有向图的邻接表更简单,每当读人一个顶点对序号 ,j> 时,仅需生成一个邻接序号为j的边表结点,将其插入到vj的出边表头部即可。 同时没个节点带权访问。 邻接表的形式说明 typedef struct node{//边表结点 ...
该算法是用C#实现的,要用Visual Studio2005
C++数据结构 AOE CPP源文件 采用数据结构中的AOE方法对图的关键路径进行计算 :建立邻接表
数据结构 c++ 图的最短路径问题 (邻接表) 数据结构 c++ 图的最短路径问题 (邻接表)
用图的邻接表求最短路径,用邻接表 邻接表 邻接表
领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
数据结构中的关键路径程序代码,通过邻接表及栈实现
图的邻接矩阵存储和邻接表存储 代码完整 有注释,有需要的可以下载看看,基本是图的邻接矩阵存储和邻接表存储 代码完整
使用邻接表实现图结构,无向的、有向的、无权的和有权的都可支持。
C++实现图的邻接表,利用了类模板,可以构建有向图和无向图,包含链表、图的ADT,里面附有说明文档,详细说明了主程序的测试方式。
简单的数据结构邻接表代码,包括广度优先遍历,任意两个顶点之间的所有路径,再结合课本上的内容,邻接表就可以学的很好了
//以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 int info; //顶点其余的信息 }VertexType; typedef struct { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数,弧数 VertexType vexs[MAXV...
实现图的深度和广度优先搜索 /* 邻接表的结点类型 */ typedef struct arc {int adjvex; struct arc *next;}ArcNode; typedef struct VexNode {int vertex; ArcNode *firstarc; }VerNode; typedef VerNode ...
假设图中各边的权值都相等,以邻接矩阵和邻接表为存储结构,分别写出算法: (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径 要求输出路径上的所有顶点(利用BFS遍历的思想)
数据结构那本书上的图的邻接表存储 struct node { int vertex; struct node * nextnode; };
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
在C语言下利用C语言创建AOE网,并进行拓扑排序。功能模块包含图的创建,图的输出及拓扑排序。