`

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
    /**
     * 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#有向图算法(邻接表包含关键路径、DFS、BFS、拓扑排序)

    本文将详细讲解如何使用C#语言实现有向图算法,包括邻接表、关键路径、深度优先搜索(DFS)和广度优先搜索(BFS),以及拓扑排序。 首先,我们要理解有向图的概念。有向图是由顶点(节点)和边组成的,边具有方向性...

    逆邻接表快速实现拓扑排序

    本篇将详细介绍如何使用逆邻接表来快速实现拓扑排序。 首先,我们需要理解什么是逆邻接表。在图的表示中,邻接表是一种常见的数据结构,它为每个顶点存储其相邻顶点的列表。对于有向图,正向邻接表记录了每条边的...

    基于邻接表存储的图的拓扑排序算法

    基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助

    图的最短路径、拓扑排序和关键路径

    "图的最短路径、拓扑排序和关键路径" 图的最短路径是图论中的一种重要概念,它是指从图的一顶点到另一顶点的路径中,所经过的边的数目最少的那条路径。这种路径也可以称作最短距离或最短路径长度。在无权图中,图的...

    实现图的邻接矩阵和邻接表存储

    在编程中,有多种方法来存储图,其中两种常用的方法是邻接矩阵和邻接表。这两种方法各有优缺点,适用于不同类型的图和不同的操作需求。 邻接矩阵是一种二维数组,其中的每个元素代表两个顶点之间是否存在边。如果...

    C++版数据结构关键路径代码通过邻接表及栈实现

    在本篇文章中,我们将深入探讨一种特定的图算法——关键路径法(Critical Path Method, CPM),并了解如何使用邻接表和栈来实现这一算法。 #### 邻接表与栈的运用 邻接表是一种存储图的高效方式,它对于无向图或有...

    图的邻接表实现.rar

    在实际应用中,使用邻接表实现的图可以有效地进行深度优先搜索(DFS)和广度优先搜索(BFS),并支持多种图算法,如最短路径计算(Dijkstra算法或Floyd-Warshall算法)、拓扑排序等。此外,由于类模板的使用,此实现...

    图的邻接表的实现带权路径

    建立有向图的邻接表更简单,每当读人一个顶点对序号 ,j&gt; 时,仅需生成一个邻接序号为j的边表结点,将其插入到vj的出边表头部即可。 同时没个节点带权访问。 邻接表的形式说明 typedef struct node{//边表结点  ...

    【数据结构】基于紧缩图的邻接表的拓扑排序.doc

    在本次课程设计中,将使用紧缩图的邻接表来存储图中的数据,并设计实现基于紧缩图的邻接表的拓扑排序程序。 知识点6:函数原型设计 函数原型设计是指设计实现基于紧缩图的邻接表的拓扑排序程序的函数原型。在本次...

    图的邻接表存储C语言实现

    ### 图的邻接表存储与C语言实现:深入解析 #### 核心概念与背景 在数据结构领域,图是一种非常重要的非线性数据结构,它由顶点集(Vertex Set)和边集(Edge Set)组成。在图中,顶点代表数据对象,而边则表示这些...

    数据结构 图的邻接表存储

    ### 数据结构:图的邻接表存储 #### 一、引言 在计算机科学中,图是一种非线性数据结构,由顶点...通过合理的数据结构设计和算法实现,可以有效地支持图的各种基本操作和高级应用,如遍历、排序和关键路径分析等。

    AOE关键路径 邻接表存储

    C++数据结构 AOE CPP源文件 采用数据结构中的AOE方法对图的关键路径进行计算 :建立邻接表

    数据结构 c++ 图的最短路径问题 (邻接表)

    数据结构 c++ 图的最短路径问题 (邻接表) 数据结构 c++ 图的最短路径问题 (邻接表)

    拓扑排序关键路径算法C语言完整代码

    在提供的`CriticalPath.c`和`CriticalPath.h`文件中,我们可以看到一个实现拓扑排序和关键路径算法的C语言程序。这个程序可能包括以下关键部分: 1. **图数据结构**:通常使用邻接表或邻接矩阵来表示有向图。邻接表...

    【数据结构】基于紧缩图的邻接表的拓扑排序正文终稿.doc

    该课题的主要目标是设计基于紧缩图的邻接表的拓扑排序程序,采用STL的图、栈等数据结构,实现紧缩图的邻接表结构的拓扑排序。 知识点1:紧缩图的邻接表结构 紧缩图的邻接表结构是指将图的每个顶点的邻接表紧凑的...

    数据结构基于紧缩图的邻接表的拓扑排序-毕业论文.doc

    该论文的主要内容包括:紧缩邻接表的数据结构、基于紧缩图的拓扑排序算法、STL 图库的应用、紧缩图的邻接表结构的设计和实现、拓扑排序的实现等。 在数据结构方面,本文主要介绍了紧缩邻接表的数据结构,包括向量 ...

    毕业设计-数据结构基于紧缩图的邻接表的拓扑排序.doc

    本课程设计的目标是设计基于紧缩图的邻接表的拓扑排序程序,采用STL的图、栈等数据结构,实现STL的紧缩邻接表结构图类,并实现紧缩图的邻接表结构的拓扑排序。 在该课程设计中,我们首先对紧缩图的邻接表进行了深入...

    关键路径计算 C语言 邻接表实现.zip

    本资料主要探讨了如何使用C语言和邻接表数据结构来实现关键路径计算。 首先,我们需要理解邻接表数据结构。在图论中,邻接表是一种高效存储图的方式,它将每个顶点的邻居以链表的形式存储。相比于邻接矩阵,邻接表...

    图的邻接矩阵存储和邻接表存储

    图是数据结构中的一种重要...综上所述,`createadjlist.cpp`和`creatematix.cpp`文件分别实现了图的邻接表和邻接矩阵存储,为理解和操作图提供基础。通过阅读和理解这些代码,你可以更好地掌握这两种重要的图数据结构。

    新建 DOC 文档_实现图的邻接矩阵和邻接表存储_doc_图的遍历算法_

    领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...

Global site tag (gtag.js) - Google Analytics