邻接矩阵实现图的深度优先和广度优先遍历（PHP）

图的遍历分为两种
深度优先DFS
广度优先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;

//广度优先遍历

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;

}

//深度优先遍历

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);

---

欢迎大家关注我的公众号

半亩房顶