K162

Starwalker, Stardust.

0%

图的遍历与路径记录

对图进行遍历时,我们往往会建立一个数组 vis[],用来记录是否访问过某一结点,或(在广度优先遍历时)建立一个数组 inq[] ,用来记录结点是否进入过队列。

但如果需要获得遍历过程中,从起始结点到各个结点的路径,可以通过记录结点的前驱来实现。

PHP 关联数组

在 PHP 的实现中,可以直接将数组 vis[] (或是 inq[]) 换作一个关联数组,用来记录结点前驱。其中,下一个结点 $next 作为关联数组的键,$node 当前结点为值:

1
2
3
4
$inq[ $next ] = $node;
// $inq 关联数组
// $next 下一个结点
// $node 当前结点,即作为下一个结点的前驱

遍历过程中,如果要确认某个结点是否被访问过(或是否进入过队列),可使用 array_key_exists(key, array) 函数,检查某一个数组中是否存在某一个键名。例如,若能在 $inq 中找到名为 $next 的键(即返回 true),那就说明 $next 已经进入过队列:

1
2
3
array_key_exists($next, $inq);
// $next 下一个结点,即关联数组的键
// $inq 关联数组

获得路径

建立一个数组 $path,用来保存结点路径, $i 为数组 $path 下标。

如果需要获得从起始结点 $start 到某一结点 $node 的路径,可以通过循环,不断寻找当前结点的前驱,同时记录到数组 $path 中:

1
2
3
4
5
6
$i = 0;
while( $node != $start ){ // 如果没有到达起始结点
$path[ $i ] = $node; // 记录到路径数组中
$node = $inq[ $node ]; // 变成前驱
$i++; // 下标 +1
}

此时数组 $path 中,起始结点在 $path 最后一位。如果需要正向序列,只要逆向输出即可!

在 C/C++ 中的实现

在 C++ 的 STL 容器中有一种 map,也应该可以实现。

map 可以将任何基本类型(包括 STL 容器),映射到任何基本类型(包括 STL 容器):

1
map<typename1, typename2> mp;

当然,在一些简单场景下,前驱的记录可以直接单纯地用一个一维的数值数组实现,类似于数组实现的静态链表。