• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[PHP]算法-邻接矩阵图的广度和深度优先遍历的PHP实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
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有路径相通的顶点,递归调用
<?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);

 

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"
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
php-nginx超时时间过短导致的post失败发布时间:2022-07-10
下一篇:
PHP实例表单数据插入数据库及数据提取用户注册验证发布时间:2022-07-10
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap