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

发布时间：2020-05-25 03:10:15 所属栏目：PHP 来源：互联网

导读：1.图的深度优先遍历类似前序遍历,图的广度优先类似树的层序遍历2.将图进行变形,根据顶点和边的关系进行层次划分,使用队列来进行遍历3.广度优先遍历的关键点是使用一个队列来把当前结点的所有下一级关联点存进去,依次进行邻接矩阵的广度优先遍历:BFS(G)for i=0

1.图的深度优先遍历类似前序遍历,2.将图进行变形,根据顶点和边的关系进行层次划分,3.广度优先遍历的关键点是使用一个队列来把当前结点的所有下一级关联点存进去,邻接矩阵的广度优先遍历:<span style="color: #000000">

BFS(G)

<span style="color: #0000ff">for i=0;inumVertexes;i++<span style="color: #000000">

visited[i]=<span style="color: #0000ff">false;<span style="color: #008000">//<span style="color: #008000">检测是否访问过

<span style="color: #0000ff">for i=0;i<G.numVertexes;i++<span style="color: #008000">//<span style="color: #008000">遍历顶点

<span style="color: #0000ff">if visited[i]==<span style="color: #0000ff">true <span style="color: #0000ff">break;<span style="color: #008000">//<span style="color: #008000">访问过的断掉

visited[i]=<span style="color: #0000ff">true <span style="color: #008000">//<span style="color: #008000">当前顶点访问

InQueue(i)      <span style="color: #008000">//<span style="color: #008000">当前顶点入队列

<span style="color: #0000ff">while(!QueueEmpty()) <span style="color: #008000">//<span style="color: #008000">当前队列不为空

i=OutQueue() <span style="color: #008000">//<span style="color: #008000">队列元素出队列

<span style="color: #0000ff">for j=0;jnumVertexes;j++ <span style="color: #008000">//<span style="color: #008000">遍历顶点

<span style="color: #0000ff">if G->arc[i][j]==1 && !visited[j] <span style="color: #008000">//<span style="color: #008000">当前顶点与其他顶点存在关系并且未被访问

visited[j]=<span style="color: #0000ff">true <span style="color: #008000">//<span style="color: #008000">标记此顶点

InQueue(j)      <span style="color: #008000">//<span style="color: #008000">此顶点入队列,会排在后面等前面一层的全遍历完才会遍历这个

<span style="color: #000000">

深度优先遍历DFS:<span style="color: #000000">

DFSTravserse G

<span style="color: #0000ff">for i=0;i<G.xNum;i++

<span style="color: #0000ff">if !<span style="color: #000000">visted[i]

DFS(G,<span style="color: #000000">i)

DFS G,<span style="color: #000000">i

visted[i]=<span style="color: #0000ff">true

<span style="color: #0000ff">print G.<span style="color: #000000">vexs[i]

<span style="color: #0000ff">if G.arc[i][j]==1 && !<span style="color: #000000">visited[j]

DFS(G,<span style="color: #000000">j)
图的物理存储的实现:<span style="color: #000000">

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

有向图的存储方法:<span style="color: #000000">十字链表

无向图存储的优化:<span style="color: #000000">邻接多重表
图的遍历:

1.从图中某一顶点出发访遍图中其余顶点,<span style="color: #000000">且使每个顶点仅被访问一次

2.需要给访问过的顶点打上标记,设置个数组visited[n],<span style="color: #000000">访问过后设置为1

3.遍历次序:<span style="color: #000000">深度优先遍历和广度优先遍历

深度优先遍历DFS:

1.类似走迷宫右手定则,走一个做标记,一直往右走,直到重复了,<span style="color: #000000">就退回上一个顶点

2.从某个顶点v出发访问和v有路径相通的顶点,递归调用

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

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!