PHP实现图的邻矩阵及普利姆算法(Prim)

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