图的遍历与路径记录

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

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

PHP 关联数组

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

$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 中：

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

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