图论（7）：图的遍历 - 广度优先和深度优先算法
定义
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个访问的过程叫做图的遍历(Traversing Graph)。且图的遍历算法是一个比较基础的算法，前面我们介绍的有向无环图的依赖排序（拓扑排序）、关键路径等算法都需要基于该算法。
通常，有两条遍历图的路径：广度优先搜索和深度优先搜索，且对无向图和有向图都适用。
另外，由于Guava中的Graph模块已对这两种图的遍历算法进行了实现，且其代码是我所见过最完美的实现了。因此，本篇文章不打算重新实现一个遍历算法，而是以Guava的实现为基础进行算法分析和验证。它的具体实现代码文件为：https://github.com/google/guava/blob/master/android/guava/src/com/google/common/graph/Traverser.java
广度优先遍历
也称为广度优先搜索（Breadth First Search），它类似于树的分层遍历算法（按树的深度来遍历，深度为1的节点、深度为2的节点...）。其定义如下：
假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发并依次访问它们的邻接点，并使“先被访问的顶点邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点重复上述过程，直至图中所有顶点均被访问到为止。
换句话说，广度优先遍历的过程是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2,...的顶点的过程。
下面演示对示例图的广度优先遍历：假设从起始点v1开始遍历，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5，及v3的邻接点v6和v7，最后访问v4的邻接点v8。于是得到节点的线性遍历顺序为：v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8，即示例图中红色箭头线为其广度优先遍历顺序。
广度优先遍历（红色箭头线及序号为遍历顺序）
算法分析
从演示示例的推演中，我们可以发现其访问顺序恰好是一个队列的出队和入队的过程：出队的节点即为当前访问的节点，紧接着将其所有的邻接点入队，为下次迭代时将要访问的预备节点。
Guava的实现思路基本也是如此，下面我们看看它的实现方式：
首先，它定义了一个抽象的广度优先遍历接口，以便有多种实现方式（下面它还有一个树状图的遍历优化实现），更重要的是它将遍历的过程封装在一个迭代器（Iterable）中返回了，仅在调用方通过next()访问返回结果时才动态输出其遍历顺序，个人觉得这是它实现的一大亮点。这样做的好处是，实际的调用过程并不消耗cpu时间（仅仅是new了一个特定类型的Iterator），而是在调用完成后在使用其结果做其他运算时（比如输出或者将其作为其他功能的输入等）才耗费计算时间。一般，我们通常的做法是函数完成遍历运算然后返回运算结果（List<N>），如果后续需要利用该结果进行其他运算时再循环遍历结果集，亦或者直接在在遍历算法的迭代中直接处理其结果，而迭代器明显优于这两种做法。
广度优先遍历接口定义为：
/**
*
* @param startNode: 遍历的起始节点
* @return 返回一个Iterable作为节点的顺序
*/
public abstract Iterable<N> breadthFirst(N startNode);
由于接口返回的是一个Iterable，那么它的实现肯定就是创建了一个Iterable了，然后实现它的iterator()接口：
@Override
public Iterable<N> breadthFirst(final N startNode) {
/**
* 创建一个匿名的Iterable，并实现iterator()接口
*/
return new Iterable<N>() {
@Override
public Iterator<N> iterator() {
/**
* 返回一个自定义的Iterator
*/
return new BreadthFirstIterator(startNode);
}
};
}
该自定义迭代器BreadthFirstIterator中，其主体实现在迭代函数next()中，每迭代一次（调用next()函数一次）返回一个以广度优先遍历为顺序的一个节点：
/**
* 声明为private私有, 可对外隐藏其内部实现，调用者仅需要
* 知道是一个Iterator即可
*/
private final class BreadthFirstIterator extends Iterator<N> {
//构建节点顺序的队列：执行入队和出队操作
private final Queue<N> queue = new ArrayDeque<>();
//用于记录节点是否访问标记，避免重复访问
private final Set<N> visited = new HashSet<>();
/**
* 构造函数时，首先从起始点入队开始
* @param root
*/
BreadthFirstIterator(N root) {
queue.add(root);
visited.add(root);
}
@Override
public boolean hasNext() {
/**
* 当队列为空时，则遍历完成，即没有后续节点了。
*/
return !queue.isEmpty();
}
@Override
public N next() {
//队头节点出队，作为当前迭代的访问节点
N current = queue.remove();
/**
* 依次将当前节点的后继节点入队，为下一次迭代做准备
*/
for (N neighbor : graph.successors(current)) {
//add()返回true时（表示第一次加入，即是第一次访问），则入队
if (visited.add(neighbor)) {
queue.add(neighbor);
}
}
return current;
}
}
上面给出了广度优先遍历算法的实现，下面写一个简单demo验证其实现结果：
//构建示例图所示的图结构（无向图）
MutableGraph<String> graph = GraphBuilder.undirected()
.nodeOrder(ElementOrder.<String>natural()).build();
graph.putEdge(V1, V2);
graph.putEdge(V1, V3);
graph.putEdge(V2, V4);
graph.putEdge(V2, V5);
graph.putEdge(V3, V6);
graph.putEdge(V3, V7);
graph.putEdge(V4, V8);
graph.putEdge(V5, V8);
graph.putEdge(V6, V7);
//测试breadthFirst()接口，从V1开始遍历
Iterable<String> bfs = Traverser.forGraph(graph).breadthFirst(V1);
//输出遍历结果: for循环（forEach）默认实现iterator的遍历next()
for (String node : iterable) {
print(node);
}
输出顺序为：
bfs graph: {V1,V3,V2,V6,V7,V5,V4,V8}
注：虽然该顺序与示例图的红色箭头线标识的顺序有所不同，但仍满足广度优先遍历的顺序，其差异主要是在选择当前节点的后继节点时 遍历后继节点的顺序不同。
而该顺序不同的主要原因是由于无向图邻接点（successors()返回的Set<T>结果）的存储结构UndirectedGraphConnections采用的是HashMap，然后通过HashMap的KeySet()（对应的是HashSet<T>）返回的节点集，但由于HashSet是不是有序的，所以导致最终的结果并没有按预先的顺序，但结果整体上满足遍历顺序的要求。
关于HashMap的顺序问题，我做了如下测试：
//返回V1的后继节点集
Set<String> successors = graph.successors(V1);
print(success);
//测试HashMap的节点顺序
Map<String, Integer> testMap = new HashMap<>();
testMap.put(V1, 0);
testMap.put(V2, 0);
testMap.put(V3, 0);
print(testMap.keySet());
测试结果如下，刚好重现了遍历顺序的差异：
successor: {V3,V2}
Map KeySet() order: {V3,V2,V1}
下面我继续来看深度优先遍历：
深度优先遍历
也称为深度优先搜索（Depth First Search），它类似于树的先根遍历（先访问树的根节点）。其定义如下：
假设从图中的某个顶点v出发，访问此节点后，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则选另选一个未曾访问的顶点作为起始点重复上述过程，直至图中的所有节点都被访问到为止。
下面演示对示例图的深度优先遍历：假设从起始点v1开始遍历，在访问了v1后，选择其邻接点v2。因为v2未曾访问过，则从v2出发进行深度优先遍历。依次类推，接着从v4、v8、v5出发进行遍历。在访问了v5后，由于v5的邻接点都已被访问，则遍历回退到v8。同样的理由，继续回退到v4、v2直至v1，此时v1的另一个邻接点v3未被访问，则遍历又从v1到v3,再继续进行下去。于是得到节点的线性顺序为：v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7，即示例图中红色箭头线为其深度优先遍历顺序。
深度优先遍历-PreOrder顺序（红色箭头线及序号为遍历顺序）
算法分析
从上述的描述可以看出，深度优先遍历的定义就是一个递归的过程，每次都以当前节点的第一个未曾访问过的邻接点进行深度优先遍历的过程。因此使用递归函数实现该算法是最直观的实现方式，但由于递归的过程是函数栈累积的过程，如果节点数较多，容易造成函数栈的溢出而导致程序崩溃，因此正常生产环境一般会使用一个栈结构（Stack）来存放遍历的节点以模拟函数栈的调用情况，以此避免递归的缺陷。
Guava的大体实现思路也是如此，使用栈结构来替代函数的递归实现。另外，Guava对深度优先遍历还进行了扩展：区分节点的访问顺序是第一次访问到节点的顺序(PreOrder)，还是访问到底后回退时的节点顺序(PostOrder)。
附上Guava的原文注释：
"Pre-order" implies that nodes appear in the {@code Iterable} in the order in which they are first visited.
"Post-order" implies that nodes appear in the {@code Iterable} in the order in which they are visited for the last time.
因此，对于深度优先遍历，Guava根据这两个场景定义了下面两个接口：
//第一次访问到节点的顺序（Pre-order）
public abstract Iterable<N> depthFirstPreOrder(N startNode);
//访问到最后，然后回退访问节点的顺序（Post-order）
public abstract Iterable<N> depthFirstPostOrder(N startNode);
它的实现与上述描述相同，也是创建了一个Iterable，然后实现它的iterator()接口，由于这两个接口相近，下面仅举例说明其中一个（depthFirstPostOrder）：
@Override
public Iterable<N> depthFirstPostOrder(final N startNode) {
/**
* 创建一个匿名的Iterable，并实现iterator()接口
*/
return new Iterable<N>() {
@Override
public Iterator<N> iterator() {
/**
* 返回一个自定义的Iterator
*/
return new DepthFirstIterator(startNode, Order.POSTORDER);
/**
* depthFirstPreOrder()遍历时也是创建了DepthFirstIterator()，只是参数换成了Order.PREORDER
*/
//return new DepthFirstIterator(startNode, Order.PREORDER);
}
};
}
该自定义迭代器DepthFirstIterator中，其主体实现在迭代函数next()中，每迭代一次（调用next()函数一次）返回一个以深度优先遍历为顺序的一个节点：
/**
* 自定义深度优先遍历的结果迭代器（AbstractIterator继承自Iterator）
*/
private final class DepthFirstIterator extends AbstractIterator<N> {
/**
* 模拟函数递归遍历节点的堆栈，每次入栈的数据是：节点-节点的邻节点集
*/
private final Deque<NodeAndSuccessors> stack = new ArrayDeque<>();
/**
* 标识节点是否已访问过
*/
private final Set<N> visited = new HashSet<>();
/**
* 指定深度优先遍历的顺序: PREORDER, POSTORDER
*/
private final Order order;
/**
* 构造函数，首先将指定的起始节点-及邻接点入栈
* @param root：起始节点
* @param order：指定遍历的顺序
*/
DepthFirstIterator(N root, Order order) {
stack.push(withSuccessors(root)); //节点-及邻接点入栈
this.order = order;
}
/**
* 基类封装的next()函数
* @return
*/
@Override
protected N computeNext() {
while (true) { //直到找到合适遍历顺序的节点
/**
* 堆栈为空时，遍历结束，返回null
*/
if (stack.isEmpty()) {
return endOfData();
}
/**
* 每次拿到栈顶的数据参与运算,且由于withSuccessors()
* 对应的邻接点也是Iterator,因此需要注意运算中是否所有
* 的邻接点都有遍历完毕。（算法核心）
*/
NodeAndSuccessors node = stack.getFirst();
/**
* Set<>.add()操作返回true时，表示为第一次加入到Set集合中
* 对应到遍历顺序 -- PREORDER。因此firstVisit标识PREORDER顺序的访问
*/
boolean firstVisit = visited.add(node.node);
/**
* 当successorIterator都遍历完毕时（!node.successorIterator.hasNext()）,
* 表示该路径已经遍历完毕了，现在需要开始回退，则该节点是回退时的节点
* 对应到遍历顺序 -- POSTORDER。因此lastVisit标识POSTORDER顺序的访问
*
*/
boolean lastVisit = !node.successorIterator.hasNext();
/**
* 当前步骤是否产生了一个可以返回的迭代节点（firstVisit | lastVisit）
*/
boolean produceNode =
(firstVisit && order == Order.PREORDER) || (lastVisit && order == Order.POSTORDER);
/**
* 如果当前节点的邻接点集都已遍历完毕时，则将该节点出栈。
* 以致下一次stack.getFirst()时获得的数据变成未访问的新数据
*/
if (lastVisit) {
stack.pop();
} else {
/**
* 如果邻接点还没遍历完毕，则每次将一个邻接点及邻接点的邻接点集合压入栈中
* 需注意该邻接点是否已有访问过
*/
N successor = node.successorIterator.next();
if (!visited.contains(successor)) {
stack.push(withSuccessors(successor));
}
}
/**
* 若当前节点满足遍历顺序（firstVisit | lastVisit）,则返回该节点。
* 否则，将继续上述栈中数据的操作，直到找到满足produceNode的节点或者栈中数据遍历完毕
*/
if (produceNode) {
return node.node;
}
}
}
/**
* 构建堆栈数据结构：节点-及邻接点
* @param node
* @return
*/
NodeAndSuccessors withSuccessors(N node) {
return new NodeAndSuccessors(node, graph.successors(node));
}
}
针对上面给出的深度度优先遍历算法实现，下面还是写一个简单demo验证其实现结果：
//构建示例图所示的图结构（无向图）
MutableGraph<String> graph = GraphBuilder.undirected()
.nodeOrder(ElementOrder.<String>natural()).build();
graph.putEdge(V1, V2);
graph.putEdge(V1, V3);
graph.putEdge(V2, V4);
graph.putEdge(V2, V5);
graph.putEdge(V3, V6);
graph.putEdge(V3, V7);
graph.putEdge(V4, V8);
graph.putEdge(V5, V8);
graph.putEdge(V6, V7);
//测试depthFirstPreOrder()接口，从V1开始遍历
Iterable<String> dfsPre = Traverser.forGraph(graph).depthFirstPreOrder(V1);
for (String node : iterable) {
print(node);
}
//测试depthFirstPostOrder()接口，从V1开始遍历
Iterable<String> dfsPost = Traverser.forGraph(graph).depthFirstPostOrder(V1);
for (String node : iterable) {
print(node);
}
输出顺序为：
dfs pre-order graph: {V1,V3,V6,V7,V2,V5,V8,V4}
dfs post-order graph: {V7,V6,V3,V4,V8,V5,V2,V1}
注：该顺序与示例图的红色箭头线标识的顺序有所不同，但仍满足深度优先遍历的顺序，其差异原因前面已经有说明过。
另外，由于图节点连接属性的复杂性（任何两个节点都可能存在连接），所以在遍历过程中需要另设一个Set<N>来记录该节点的访问标记（因为图中如果存在回路时会存在重复访问的问题）；为此，Guava对于明确不存在回路的树形图（即有向无环图）提供了另一种更优的访问方法forTree()，不过它也是在前面介绍的三种遍历方法的基础上进行优化实现的，具体可以参考原文的前面的链接进行查看。
最后，文中示例代码的详细实现参见：https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/TestTraverser.java
参考文档
《数据结构》-- 严蔚敏
