圖的遍歷分為兩種
深度優(yōu)先DFS
廣度優(yōu)先BFS
概念不必多做解釋，下面上代碼，其實很簡單：

<?php

class Graph{

        public $vertexs;

        public $arc;

        public $num=5;

}

$G=new Graph();

for($i=0;$i<$G->num;$i++){

        $G->vertexs[$i]="V{$i}";

}

$G->arc[1][0]=9;

$G->arc[1][2]=3;

$G->arc[2][0]=2;

$G->arc[2][3]=5;

$G->arc[3][4]=1;

$G->arc[0][4]=6;

//廣度優(yōu)先遍歷

function BFS($G){

        $res=array();

        $queue=array();

        for($i=0;$i<$G->num;$i++){

                $visited[$i]=false;

        }   

        for($i=0;$i<$G->num;$i++){

                if($visited[$i]){

                        break;

                }   

                $visited[$i]=true;

                $res[]=$G->vertexs[$i];

                array_push($queue,$i);

                while(!empty($queue)){

                        $v=array_pop($queue);

                        for($j=0;$j<$G->num;$j++){

                                if($G->arc[$v][$j]>0 && !$visited[$j]){

                                        $visited[$j]=true;

                                        $res[]=$G->vertexs[$j];

                                        array_push($queue,$j);

                                }   

                        }   

                }   

        }   

        return $res;

}

//深度優(yōu)先遍歷

function DFS($G,$i){

        static $res;

        static $visited;

        if(!$visited[$i]){

                $visited[$i]=true;

                $res[]=$G->vertexs[$i];

        }

                for($j=0;$j<$G->num;$j++){

                        if($G->arc[$i][$j]>0 && !$visited[$j]){

                                $visited[$j]=true;

                                $res[]=$G->vertexs[$j];

                                DFS($G,$j);

                        }

                }

        return $res;

}

$b=BFS($G);

$d=DFS($G,1);

var_dump($b);

var_dump($d);

歡迎大家關(guān)注我的公眾號

半畝房頂