《算法导论》-- 图的广度优先搜索和深度优先搜索 + PHP实现
2018-05-02 本文已影响70人
10xjzheng
1. 广度优先搜索
在给定图G=(V, E)和一个特定的源顶点s的情况下，广度优先搜索系统地探索G中的边，以期发现可从s到达的所有定点，并计算s到达所有这些可达顶点之间的距离（即最少的边数）。该搜索算法同时还能生成一棵根为s、且包括所有s可达顶点的广度优先树。该算法对有向图和无向图同样适用。
1.1 伪代码实现
下面的广度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点，还采用了几种另外的数据结构，对每个顶点u∈V，其色彩存储于遍历color[u]中，u的父母存于变量π[v]中，如果u没有父母(例如u=s或u尚未被发现)，则π[u]=NIL。由该算法计算出来的源顶点和顶点u之间的距离存于变量d[u]中，该算法还使用了一个先进先出的队列Q来管理所有的灰色顶点。
BFS(G, s) //G是图，s是起点，u是点，v是边
for each vertex u∈V[G]-{s}
do color[u]←WHITE
d[u]←∞
π[u]←NIL
color[s]←GRAY
d[s]←0
π[s]←NIL
Q←∅
ENQUEUE(Q,s)
while Q≠∅
do u←DEQUEUE(Q)
for each v∈Adj[u]
do if color[v]=WHITE
then color[v]∈GRAY
d[v]←d[u]+1
π[v]←u
ENQUEUE(Q,v)
color[u]←BLACK
1.2 伪代码的执行过程
image.png
2. 深度优先搜索
算法搜索策略是尽可能“深”地搜索一个图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点时为止，如果还存在未被发现的顶点，则选择其中一个作为源顶点，并重复以上过程。整个过程反复进行，直到所有的顶点都已被发现为止。
2.1 伪代码实现
使用的数据结构跟深度优先类型，特殊之处是为每个顶点加盖时间戳。当顶点v有两个时间戳：当顶点v第一次发现（并置成灰色）时，记录下第一个时间戳d[v]，当结束检查v的邻接表（并置v为黑色）时，记录下第二个时间戳f[v]。许多图算法中都用了时间戳，它们对推算深度优先搜索的进行情况有很大的帮助。
DFS(G)
for each vertex u∈V[G]
do color[u]←WHITE
π[u]←NIL
time←0
for each vertex u∈V[G]
do if color[u]=WHITE
then DFS-VISIT(u)
DFS-VISIT(u)
color[u] ← GRAY
time←time+1
d[u]←time
for each v∈Adj[u]
do if color[v]=WHITE
then π[v]←u
DFS-VISIT(v)
color[u]←BLACK
f[u]←time←time+1
2.2 伪代码的执行过程
image.png
3. PHP实现广度优先搜索和深度优先搜索
3.1 原图：
image.png
3.2 代码示例
<?php
/**
* 节点
* Class Node
*/
class Node {
public $d; //广度搜索时表示距离，深度搜索表示变灰色时的时间戳
public $color;//色彩
public $p;//父节点
public $val; //节点值
public $time; //变黑色时的时间戳
public $linkNodes = [];//连接的节点
public function __construct($val)
{
$this->val = $val;
}
}
/**
* 无向图
* Class Graph
*/
class Graph {
/**
* 建图
* @param array $data 数组
*/
public function buildGraph($data)
{
$nodeVals = array_keys($data);
$nodes = [];
foreach ($nodeVals as $nodeVal) {
$nodes[$nodeVal] = new Node($nodeVal);
}
foreach ($data as $key => $vals) {
foreach ($vals as $val) {
if(isset($nodes[$val])) {
$nodes[$key]->linkNodes[] = $nodes[$val];
}
}
}
return $nodes;
}
/**
* 广度搜索
* @param array $graphNodes
* @param Node $node
*/
public function BFS($graphNodes, $node)
{
$result = [];
foreach ($graphNodes as $item) {
$item->color = 'WHITE';
$item->d = 0;
$item->p = null;
}
$node->color = 'GRAY';
$node->p = NULL;
$node->d = 0;
$queue = [];
array_push($queue, $node);
while (!empty($queue)) {
$u = array_shift($queue);
foreach ($u->linkNodes as $linkNode) {
if($linkNode->color == 'WHITE') {
$linkNode->color = 'GRAY';
$linkNode->d = $u->d + 1;
$linkNode->p = $u;
array_push($queue, $linkNode);
}
}
$u->color = 'BLACK';
array_push($result, $u);
}
return $result;
}
/**
* 深度搜索
* @param array $graphNodes
*/
public function DFS($graphNodes)
{
$result = [];
foreach ($graphNodes as $graphNode) {
$graphNode->color = 'WHITE';
$graphNode->p = NULL;
}
$time = 0;
foreach ($graphNodes as $graphNode) {
if($graphNode->color == 'WHITE') {
$this->DFSVisit($graphNode, $time, $result);
}
}
return $result;
}
/**
* 深度遍历节点
* @param Node $u
*/
public function DFSVisit($u, $time, &$result)
{
$result[] = $u;
$u->color = 'GRAY';
$time = $time + 1;
$u->d = $time;
foreach ($u->linkNodes as $linkNode) {
if($linkNode->color == 'WHITE') {
$linkNode->p = $u;
$this->DFSVisit($linkNode, $time, $result);
}
}
$u->color = 'BLACK';
$u->time = $time + 1;
}
}
$data = [
'a' => ['b', 'f'],
'b' => ['a', 'c', 'd'],
'c' => ['b', 'd', 'e'],
'd' => ['b', 'c'],
'e' => ['c'],
'f' => ['a', 'g', 'h'],
'g' => ['f', 'h'],
'h' => ['f', 'g']
];
$obj = new Graph();
$graphNodes = $obj->buildGraph($data);
//广度优先遍历结果
$bfsResult = $obj->BFS($graphNodes, current($graphNodes));
//深度优先遍历结果
$dfsResult = $obj->DFS($graphNodes);
3.3 结果
-
广度优先搜索结果：a->b->f->c->d->g->h->e
a.png
-
深度优先搜索结果：a->b->c->d->e->f->g->h
a.png
