`

PHP实现克鲁斯卡尔(kruscal)算法

阅读更多
<?php
    require 'edge.php';
    $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
    $b = array('ab'=>'10', 'af'=>'11', 'gb'=>'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 Edge($a, $b);
    print_r($test->kruscal());
?>



<?php 
    /**
     * 边集数组
     *
     * @author zhaojiangwei
     * @since 2011/11/4 16:09
     *
     */

    //边集数组的边类
    class EdgeArc{
        private $begin;//起始点
        private $end;//结束点
        private $weight;//权值

        public function EdgeArc($begin, $end, $weight){
            $this->begin = $begin;
            $this->end = $end;
            $this->weight = $weight;
        }

        public function getBegin(){
            return $this->begin;
        }

        public function getEnd(){
            return $this->end;
        }

        public function getWeight(){
            return $this->weight;
        }
    }


class Edge{
    //边集数组实现图

    private $vexs;//顶点集合
    private $arc;//边集合
    private $arcData;//要构建图的边信息
    private $krus;//kruscal算法时存放森林信息

    public function Edge($vexsData, $arcData){
        $this->vexs = $vexsData;
        $this->arcData = $arcData;
        $this->createArc();
    }

    //创建边
    private function createArc(){
        foreach($this->arcData as $key=>$value){
            $key = str_split($key);
            $this->arc[] = new EdgeArc($key[0], $key[1], $value);
        }
    }

    //对边数组按权值排序
    public function sortArc(){
        $this->quicklySort(0, count($this->arc) - 1, $this->arc); 
        return $this->arc; 
    }

    //采用快排
    private function quicklySort($begin, $end, & $item){
        if($begin < 0 || ($begin >= $end))
            return;
        
        $key = $this->excuteSort($begin, $end, $item);
        $this->quicklySort(0, $key - 1, $item); 
        $this->quicklySort($key + 1, $end, $item);
    }

    private function excuteSort($begin, $end, & $item){
        $key = $item[$begin];
        $left = array();
        $right = array();
         
        for($i = ($begin + 1); $i <= $end; $i ++){
            if($item[$i]->getWeight() <= $key->getWeight()){
                $left[] = $item[$i];   
            }else{
                $right[] = $item[$i];
            }
        }
        
        $return = $this->unio($left, $right, $key);
        
        $k = 0;
        for($i = $begin; $i <= $end; $i ++){
            $item[$i] = $return[$k];
            $k ++;
        }

        return $begin + count($left);
    }

    private function unio($left, $right, $key){
        return array_merge($left, array($key), $right);
    }

    //kruscal算法
    public function kruscal(){
        $this->krus = array();
        $this->sortArc();

        foreach($this->vexs as $value){
            $this->krus[$value] = "0";
        }

        foreach($this->arc as $key=>$value){
            $begin = $this->findRoot($value->getBegin());
            $end = $this->findRoot($value->getEnd());
            
            if($begin != $end){
                $this->krus[$begin] = $end;
                echo $value->getBegin() . "-" . $value->getEnd() . ":" . $value->getWeight() . "\n";
            }
        }
    }

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


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

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

相关推荐

    Kruscal算法大合集

    Kruskal算法是一种用于解决图论中的最小生成树问题的经典算法,由约瑟夫·克拉克·克鲁斯卡尔在1956年提出。它通过贪心策略选择边,始终选择当前未加入树的边中权值最小的一条,并确保这条边不会形成环路。以下是对...

    PHP实现克鲁斯卡尔算法实例解析

    最后,Edge类中实现了kruscal算法方法,该方法返回一个最小生成树的结果。 实例中定义了一个名为“edge.php”的文件,其中包含了Edge类和EdgeArc类的定义。在主文件中首先引入了edge.php文件,定义了顶点数组a和边...

    kruscal 与Prim算法求解最小生成树

    在`KruskalMST`文件中,可以找到实现克鲁斯卡尔算法的C++代码,包括边的结构体定义、并查集的实现以及算法的主逻辑。 **2. Prim's Algorithm(普里姆算法)** 普里姆算法从一个顶点开始,逐步添加边,使得每次添加...

    最短路径选择算法(prim kruscal)

    在上面的代码中,UndirectedGraph 类的 Kruscal 函数实现了 Kruscal 算法,该函数首先将图中的所有边排序,然后逐步添加边,直到生成树的权值最小。在添加每条边时,使用 UnionSet 类来判断是否会形成环,如果不会...

    最小生成树

    在给出的代码中,最小生成树的实现采用了克鲁斯卡尔(Kruskal)算法。克鲁斯卡尔算法的基本思想是按边的权重从小到大排序,然后依次选择未形成环的边加入到当前的生成树中。为了避免在添加边时形成环,我们需要用到...

    c语言数据结构算法演示(Windows版)

     克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...

    严蔚敏 数据结构算法演示(Windows版)软件

     克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...

    学习数据结构算法必备

     克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...

    数据结构算法演示(Windows版)

     克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...

    翻转课堂在数据结构课程中的应用.pdf

    以数据结构中的“最小生成树”教学内容为例,翻转课堂的应用可以这样实施:首先,教师制作关于普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法的教学视频,并设置相关的在线测试题目。学生在课前观看视频,并完成在线...

    用c描述的数据结构演示软件

     克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method...

    数据结构演示软件

     克鲁斯卡尔算法(Kruscal) (5)求关节点和重连通分量(Get_artical) (6)求最短路径  弗洛伊德算法(shortpath_Floyd)  迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_...

Global site tag (gtag.js) - Google Analytics