php如何实现邻接矩阵图的广度和深度优先遍历（代码）

内容导读

收集整理的这篇技术教程文章主要介绍了php如何实现邻接矩阵图的广度和深度优先遍历（代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2725字，纯文字阅读大概需要4分钟。

内容图文

本篇文章给大家带来的内容是关于php如何实现邻接矩阵图的广度和深度优先遍历（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

1、图的深度优先遍历类似前序遍历,图的广度优先类似树的层序遍历
2、将图进行变形,根据顶点和边的关系进行层次划分,使用队列来进行遍历
3、广度优先遍历的关键点是使用一个队列来把当前结点的所有下一级关联点存进去,依次进行

邻接矩阵的广度优先遍历:

BFS(G)for i=0;i<G->numVertexes;i++visited[i]=false;//检测是否访问过for i=0;i<G.numVertexes;i++//遍历顶点if visited[i]==true break;//访问过的断掉visited[i]=true //当前顶点访问InQueue(i)      //当前顶点入队列while(!QueueEmpty()) //当前队列不为空i=OutQueue() //队列元素出队列for j=0;j<G->numVertexes;j++ //遍历顶点if G->arc[i][j]==1 && !visited[j] //当前顶点与其他顶点存在关系并且未被访问visited[j]=true //标记此顶点InQueue(j)      //此顶点入队列,会排在后面等前面一层的全遍历完才会遍历这个

深度优先遍历DFS:

DFSTravserse G    for i=0;i<G.xNum;i++        if !visted[i]            DFS(G,i)DFS G,i    visted[i]=true    print G.vexs[i]    if G.arc[i][j]==1 && !visited[j]        DFS(G,j)

图的物理存储的实现:

邻接矩阵 邻接链表 十字链表 邻接多重表

有向图的存储方法:十字链表

无向图存储的优化:邻接多重表

图的遍历:

1、从图中某一顶点出发访遍图中其余顶点,且使每个顶点仅被访问一次
2、需要给访问过的顶点打上标记,设置个数组visited[n],访问过后设置为1
3、遍历次序:深度优先遍历和广度优先遍历

深度优先遍历DFS:

1、类似走迷宫右手定则,走一个做标记,一直往右走,直到重复了,就退回上一个顶点
2、从某个顶点v出发访问和v有路径相通的顶点,递归调用

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

array(5) {  [0]=>  string(2) "V0"  [1]=>  string(2) "V4"  [2]=>  string(2) "V1"  [3]=>  string(2) "V2"  [4]=>  string(2) "V3"}array(5) {  [0]=>  string(2) "V1"  [1]=>  string(2) "V0"  [2]=>  string(2) "V4"  [3]=>  string(2) "V2"  [4]=>  string(2) "V3"}

以上就是php如何实现邻接矩阵图的广度和深度优先遍历（代码）的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的php如何实现邻接矩阵图的广度和深度优先遍历（代码）全部内容，希望文章能够帮你解决php如何实现邻接矩阵图的广度和深度优先遍历（代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。