PHP实现图的邻接矩阵_PHP_编程开发_程序员俱乐部

    <?php  
        //调用  
        require 'mGraph.php';  
        $a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');  
        $b = array('ab', 'bc', 'be', 'cd', 'df', 'fg', 'gh', 'ga', 'hj', 'gi');  
      
        $test = new MGraph($a, $b);  
        print_r($test->bfs());  
    ?>  

<?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;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值 
        
        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] = 0;
                }
            }
        }

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

        //一般遍历
        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);
        }
    }

?>