`

PHP实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法

阅读更多
<?php
    require 'mGraph.php';
    $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
    $b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');//键为边,值权值
     
    $test = new MGraph($a, $b);
    print_r($test->prim());
?>



mGraph.php
<?php
    /**
     * PHP 实现图邻接矩阵
     *
     * @author zhaojiangwei 
     * @since 2011/10/31 17:23
     */

    class MGraph{
        private $vexs; //顶点数组
        private $arc; //边邻接矩阵,即二维数组       
        private $arcData; //边的数组信息
        private $direct; //图的类型(无向或有向)
        private $hasList; //尝试遍历时存储遍历过的结点
        private $queue; //广度优先遍历时存储孩子结点的队列,用数组模仿
        private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值 
        private $primVexs; //prim算法时保存顶点
        private $primArc; //prim算法时保存边
        private $krus;//kruscal算法时保存边的信息 
        
        public function MGraph($vexs, $arc, $direct = 0){
            $this->vexs = $vexs;
            $this->arcData = $arc;
            $this->direct = $direct;
            $this->initalizeArc();
            $this->createArc(); 
        }

        private function initalizeArc(){
            foreach($this->vexs as $value){
                foreach($this->vexs as $cValue){
                    $this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity);
                }
            }
        }

        //创建图 $direct:0表示无向图,1表示有向图
        private function createArc(){
            foreach($this->arcData as $key=>$value){
                $strArr = str_split($key);
                $first = $strArr[0];
                $last = $strArr[1];
                 
                $this->arc[$first][$last] = $value;
                if(!$this->direct){
                    $this->arc[$last][$first] = $value; 
                }
            }
        }

        //floyd算法
        public function floyd(){
            $path = array();//路径数组
            $distance = array();//距离数组

            foreach($this->arc as $key=>$value){
                foreach($value as $k=>$v){
                    $path[$key][$k] = $k;
                    $distance[$key][$k] = $v;
                }
            }

            for($j = 0; $j < count($this->vexs); $j ++){
                for($i = 0; $i < count($this->vexs); $i ++){
                    for($k = 0; $k < count($this->vexs); $k ++){
                        if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){
                            $path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]];
                            $distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]];
                        }
                    }
                }
            }

            return array($path, $distance);
        }

        //djikstra算法
        public function dijkstra(){
            $final = array();
            $pre = array();//要查找的结点的前一个结点数组
            $weight = array();//权值和数组
            foreach($this->arc[$this->vexs[0]] as $k=>$v){
                $final[$k] = 0;
                $pre[$k] = $this->vexs[0];
                $weight[$k] = $v;
            }

            $final[$this->vexs[0]] = 1;
            
            for($i = 0; $i < count($this->vexs); $i ++){
                $key = 0;
                $min = $this->infinity;

                for($j = 1; $j < count($this->vexs); $j ++){
                    $temp = $this->vexs[$j];
                    if($final[$temp] != 1 && $weight[$temp] < $min){
                        $key = $temp;
                        $min = $weight[$temp]; 
                    }
                }

                $final[$key] = 1;
            
                for($j = 0; $j < count($this->vexs); $j ++){
                    $temp = $this->vexs[$j];
                    if($final[$temp] != 1 && ($min + $this->arc[$key][$temp]) < $weight[$temp]){
                        $pre[$temp] = $key;
                        $weight[$temp] = $min + $this->arc[$key][$temp];
                    }
                }
            }

            return $pre;
        }

        //kruscal算法
        private function kruscal(){
            $this->krus = array();
            
            foreach($this->vexs as $value){
                $krus[$value] = 0;   
            }

            foreach($this->arc as $key=>$value){
                $begin = $this->findRoot($key);

                foreach($value as $k=>$v){
                    $end = $this->findRoot($k);
                    if($begin != $end){
                        $this->krus[$begin] = $end; 
                    }
                }
            } 
        }

        //查找子树的尾结点
        private function findRoot($node){
            while($this->krus[$node] > 0){
                $node = $this->krus[$node];
            }
        
            return $node;
        }



        //prim算法,生成最小生成树
        public function prim(){
            $this->primVexs = array();
            $this->primArc = array($this->vexs[0]=>0);
            
            for($i = 1; $i < count($this->vexs); $i ++){
                $this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]];
                $this->primVexs[$this->vexs[$i]] = $this->vexs[0];
            }

            for($i = 0; $i < count($this->vexs); $i ++){
                $min = $this->infinity;
                $key;

                foreach($this->vexs as $k=>$v){
                    if($this->primArc[$v] != 0 && $this->primArc[$v] < $min){
                        $key = $v;
                        $min = $this->primArc[$v];
                    }
                }

                $this->primArc[$key] = 0;

                foreach($this->arc[$key] as $k=>$v){
                    if($this->primArc[$k] != 0 && $v < $this->primArc[$k]){
                        $this->primArc[$k] = $v;  
                        $this->primVexs[$k] = $key; 
                    }
                }
            }

            return $this->primVexs;
        }

        //一般算法,生成最小生成树
        public function bst(){
            $this->primVexs = array($this->vexs[0]);
            $this->primArc = array();

            next($this->arc[key($this->arc)]); 
            $key = NULL;
            $current = NULL;

            while(count($this->primVexs) < count($this->vexs)){
                foreach($this->primVexs as $value){
                    foreach($this->arc[$value] as $k=>$v){
                        if(!in_array($k, $this->primVexs) && $v != 0 && $v != $this->infinity){
                            if($key == NULL || $v < current($current)){
                                $key = $k;
                                $current = array($value . $k=>$v);
                            }
                        }

                    }
                }

                $this->primVexs[] = $key;
                $this->primArc[key($current)] = current($current);
                $key = NULL;
                $current = NULL;
            }

            return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc);
        }

        //一般遍历
        public function reserve(){
            $this->hasList = array();

            foreach($this->arc as $key=>$value){
                if(!in_array($key, $this->hasList)){
                    $this->hasList[] = $key;
                }

                foreach($value as $k=>$v){
                    if($v == 1 && !in_array($k, $this->hasList)){
                        $this->hasList[] = $k;   
                    }
                }
            }

            foreach($this->vexs as $v){
                if(!in_array($v, $this->hasList))
                    $this->hasList[] = $v;
            }

            return implode($this->hasList);
        }

        //广度优先遍历
        public function bfs(){
            $this->hasList = array();
            $this->queue = array();
            
            foreach($this->arc as $key=>$value){
                if(!in_array($key, $this->hasList)){
                    $this->hasList[] = $key;
                    $this->queue[] = $value;

                    while(!empty($this->queue)){
                        $child = array_shift($this->queue);
                        
                        foreach($child as $k=>$v){
                            if($v == 1 && !in_array($k, $this->hasList)){
                                $this->hasList[] = $k;
                                $this->queue[] = $this->arc[$k];   
                            }
                        }
                    }
                }
            }

            return implode($this->hasList);
             
        }

        //执行深度优先遍历
        public function excuteDfs($key){
            $this->hasList[] = $key;  

            foreach($this->arc[$key] as $k=>$v){
                if($v == 1 && !in_array($k, $this->hasList))
                    $this->excuteDfs($k);   
            }
        }

        //深度优先遍历
        public function dfs(){
            $this->hasList = array();

            foreach($this->vexs as $key){
                if(!in_array($key, $this->hasList)) 
                    $this->excuteDfs($key); 
            }

            return implode($this->hasList);
        }

        //返回图的二维数组表示
        public function getArc(){
            return $this->arc;
        }

        //返回结点个数
        public function getVexCount(){
            return count($this->vexs);
        }
    }

?>
分享到:
评论
发表评论

文章已被作者锁定,不允许评论。

相关推荐

    图的邻接矩阵表示的各种算法

    本文将深入探讨图的邻接矩阵表示以及其中涉及的三种核心算法:迪杰斯特拉算法、普里姆算法和克鲁斯卡尔算法,并提供C++实现。 1. **图的邻接矩阵表示**: 邻接矩阵是一种二维数组,用于存储图中顶点之间的连接信息...

    最短路径算法

    根据提供的文件内容,本文将详细解释两种经典的最短路径算法:迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,并通过具体的示例代码来展示这两种算法的应用场景及其工作原理。 ### 迪杰斯特拉(Dijkstra)...

    C++算法:图算法 (第3版)_0

    接下来,书中可能会深入讨论关键的图算法,例如迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd-Warshall)算法,用于求解单源最短路径问题;普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法,用于找出图的最小生成树...

    C算法 V(第二卷 图算法

    图算法中还有一些重要的算法,例如最短路径算法,如迪杰斯特拉算法(Dijkstra's algorithm)、贝尔曼-福特算法(Bellman-Ford algorithm)以及弗洛伊德算法(Floyd-Warshall algorithm)。这些算法能够帮助我们找到...

    图算法-最小生成树和单源顶点最短路径

    1. **迪杰斯特拉算法(Dijkstra's Algorithm)**:从源顶点开始,通过逐步扩展最短路径,更新所有顶点的最短路径。它利用优先队列(如二叉堆)来存储待处理的顶点,并保证每次取出的都是当前未处理顶点中最短路径的...

    算法参考资料Graph-theoreticalgorithms

    2. 最短路径算法:用于计算图中两个节点间的最短路径,其中最著名的是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd-Warshall)算法。 3. 最小生成树算法:用于在无向连通图中找到一棵包含所有顶点的树,这棵树的边...

    数据结构与算法分析–C++描述(第3版)

    - 最短路径算法:学习诸如迪杰斯特拉(Dijkstra)算法、贝尔曼-福特(Bellman-Ford)算法、弗洛伊德(Floyd)算法等计算图中路径的算法。 - 最小生成树算法:了解普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。...

    图有关的所有算法

    11. **Dijkstra算法**:迪杰斯特拉算法是最著名的求解单源最短路径的算法,特别适合于边的权重为非负的情况。它使用优先队列(通常用堆实现)来选取当前距离源点最近的顶点。 12. **拓扑排序**:拓扑排序是对有向无...

    最小生成树问题:给定一个无向图,求最小生成树

    不过,可以预期代码会涉及图的表示(如邻接矩阵或邻接表)、排序算法(如快速排序或归并排序)以及判断环路的条件检查等核心部分。对于学习和理解最小生成树,你可以通过阅读和分析代码来加深对这些算法的理解。

    ACM算法集锦(实现代码)

    4. **Dijkstra's Algorithm**(迪杰斯特拉算法):用于寻找图中从源点到所有其他顶点的最短路径。它通常结合堆或优先队列来实现,每次处理当前最短距离的顶点。 5. **Floyd-Warshall Algorithm**(弗洛伊德-沃瑟曼...

    Graph图数据结构

    图算法还包括迪杰斯特拉算法(Dijkstra's Algorithm)用于找到单源最短路径,弗洛伊德算法(Floyd-Warshall Algorithm)用于求解所有顶点对之间的最短路径,以及克鲁斯卡尔(Kruskal's Algorithm)和普里姆(Prim's ...

    图论的算法与程序设计

    3. **迪杰斯特拉算法(Dijkstra's Algorithm)**:这是一种单源最短路径算法,适用于加权有向图。它通过逐步扩展最短路径树来找到从源节点到所有其他节点的最短路径。 4. **弗洛伊德-沃普斯算法(Floyd-Warshall ...

    数据结构第五章图习题.pdf

    8. **最短路径问题**:迪杰斯特拉算法(Dijkstra's algorithm)用于求解单源最短路径,要求边权非负;Floyd-Warshall算法可以处理有负权边但不允许负权环的情况。 9. **关键路径**:在有向无环图(AOE网)中,关键...

    Class-Files.rar_algorithms

    常见的图算法有深度优先搜索(DFS)、广度优先搜索(BFS)、迪杰斯特拉(Dijkstra)最短路径算法、弗洛伊德(Floyd-Warshall)所有对最短路径算法、普里姆(Prim)最小生成树算法、克鲁斯卡尔(Kruskal)最小生成树算法等。...

    信息学竞赛(黑书)配套课件--刘汝佳

    5. **最短路径算法**:迪杰斯特拉(Dijkstra)、弗洛伊德(Floyd-Warshall)和贝尔曼-福特(Bellman-Ford)算法,这些都是求解单源最短路径问题的重要方法,课件会详细解析它们的实现和适用条件。 6. **最小生成树*...

    数据结构第五章图习题.docx

    - 求解最短路径的迪杰斯特拉算法、最小生成树的普里姆算法和克鲁斯卡尔算法等,需要具体题目数据才能进行详细步骤分析。 这些知识点是图论的基础,对于理解和解决复杂网络问题至关重要,不仅在理论研究中重要,也...

    数据结构-3期(KC002) 图的结构分析与应用.docx

    - 迪杰斯特拉算法(Dijkstra's Algorithm):求单源最短路径,使用贪心策略,每次选取当前未访问顶点中最短路径可达的顶点。 - 弗洛伊德算法(Floyd-Warshall Algorithm):求每对顶点间的最短路径,通过动态规划...

    Graph_cpp:C ++图论算法

    - **迪杰斯特拉算法(Dijkstra's Algorithm)**:用于计算带权重的有向图中源节点到其他所有节点的最短路径。 - **贝尔曼-福特算法(Bellman-Ford Algorithm)**:不仅可以处理非负权重的图,还能检测负权环。 - ...

Global site tag (gtag.js) - Google Analytics