php实现图的邻接表_PHP_编程开发_程序员俱乐部

<?php
    //调用
    require 'alGraph.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 ALGraph($a, $b);
    print_r($test->bfs());
?>

<?php
   /**
     * PHP实现图的邻接表
     * 
     * @author zhaojiangwei
     * @since  2011/11/1 16:00
     */

    //顶点类
    class Vex{
        private $data;
        private $headLink;

        public function Vex($data, $headLink = NULL){
            $this->data = $data;
            $this->headLink = $headLink;
        }

        public function getData(){
            return $this->data;
        }

        public function getHeadLink(){
            return $this->headLink;
        }

        public function setHeadLink(& $link){
            $this->headLink = $link;
        }
    }
   
    //边类
    class Arc{
        private $key;
        private $next;
         
        public function Arc($key, $next = NULL){
            $this->key= $key;
            $this->next = $next; 
        }

        public function getKey(){
            return $this->key;
        }

        public function getNext(){
            return $this->next;
        }

        public function setNext($next){
            $this->next = $next;
        }
    }
    
    //邻接表类
    class ALGraph{
        private $vexsData;
        private $vexs;
        private $arcData;
        private $excuteDfsResult;//深度优先遍历后的字符串结果
        private $hasList; //遍历时储存遍历过的结点下标
        private $queue; //广度优先遍历时的存储队列
        
        public function ALGraph($vexsData, $arcData){
            $this->vexsData = $vexsData;
            $this->arcData = $arcData;

            $this->createHeadList();
            $this->createArc(); 
        }

        //创建顶点数组
        private function createHeadList(){
            foreach($this->vexsData as $value){
                $this->vexs[] = new Vex($value); 
            }
        }

        //创建边表
        private function createArc(){
            foreach($this->arcData as $value){
                $str = str_split($value);
                
                $this->createConnect($str[0], $str[1]);
                $this->createConnect($str[1], $str[0]);
            }
        }

        //依附于边的俩顶点建立关系
        private function createConnect($first, $last){
            $firstNode = & $this->vexs[$this->getVexByValue($first)];
            $lastNode = new Arc($this->getVexByValue($last));

            $lastNode->setNext($firstNode->getHeadLink());
            $firstNode->setHeadLink(& $lastNode);
        }

        //根据顶点的值返回顶点在顶点数组中的下标
        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;
        }
    }

?>