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()); 
?> 
alGraph.php 

    //顶点类 
    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(!emptyempty($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; 
        } 
    } 
?>