DFS(Depth-First Search)和BFS(Breadth-First Search)是两种用于访问图(graph)中节点最普遍的两种方法。在我的日常编程中，使用的graph的绝大部分都是树(tree). Tree是一种connected acyclic graph - 连通(即从一个节点一定有路径到其他任何节点)的无循环图. 本文所述内容仅限于tree, 不适用于graph.
DFS 深度优先
假设右边的树代表一个公司的组织架构，每个node是一个部门。若要计算部门c的总收入，我们必须先知道e和f的，而要知道e的总收入我们必须先知道g和h，这就是典型的深度优先。深度优先通过递归来实现，代码如下：
|
visitDFS(a); // visit from the root
// performs DFS from the given node
public void visitDFS(Node nodeStart) {
// (1) Entering node - pre-order walk
for(Node child : nodeStart.children) {
visitDFS(child); // recursive call
}
// (2) Leaving node - post-order walk
System.out.println("DFS: " + nodeStart.nodeName);
}
|
在代码中，我做了两个标记(1)和(2). 在(1)处，当前节点的所有下属节点尚未被访问，而在(2)处，其所有下属节点均被处理完毕。若要计算部门收入，很明显是在(2)处。上面代码打印结果是：d b g h e f c a
BFS 广度优先
假设我们要打印各部门收入报表给CEO，因为每个部门收入数据较多，CEO倾向先看各大部门(只有对某部门数据有疑惑时，才看小部门), 这样情况下是先打印大部门，再打印小部门，低等级部门后打印，这就是广度优先的情况。graph的BFS算法较繁琐，但tree的BFS就非常简单了：
|
visitBFS(a); // visit from the root
// performs BFS from the given node
public void visitBFS(Node nodeStart) {
List<NODE> pendingExplore = new ArrayList<NODE>(); // list of nodes pending exploration
pendingExplore.add(nodeStart);
while(pendingExplore.size() > 0) {
Node currentNode = pendingExplore.remove(0);
System.out.println("BFS: " + currentNode.nodeName);
pendingExplore.addAll(currentNode.children); // (3)
}
}
|
上面代码打印结果: a b c d e f g h. 有时同级部门之间还有顺序，譬如重要产品部门比技术支持部门往往排序靠前，要实现这个非常简单，在(3)处，将子节点添加到pendingExplore之前进行sort即可。
附：测试程序的完整代码：
|
public class TestTree {
public Node a;
@SuppressWarnings("unused")
public TestTree() {
// Construct the tree.
a = new Node("a");
Node b = a.createChildNode("b");
Node c = a.createChildNode("c");
Node d = b.createChildNode("d");
Node e = c.createChildNode("e");
Node f = c.createChildNode("f");
Node g = e.createChildNode("g");
Node h = e.createChildNode("h");
}
public void testDFS() {
System.out.println("Testing DFS");
visitDFS(a); // visit from the root
}
// performs DFS from the given node
public void visitDFS(Node nodeStart) {
// Entering node - pre-order walk
for (Node child : nodeStart.children) {
visitDFS(child); // recursive call
}
// Leaving node - post-order walk
System.out.println("DFS: " + nodeStart.nodeName);
}
public void testBFS() {
System.out.println("Testing BFS");
visitBFS(a); // visit from the root
}
// performs BFS from the given node
public void visitBFS(Node nodeStart) {
List<Node> pendingExplore = new ArrayList<Node>(); // list of nodes
// pending
// exploration
pendingExplore.add(nodeStart);
while (pendingExplore.size() > 0) {
Node currentNode = pendingExplore.remove(0);
System.out.println("BFS: " + currentNode.nodeName);
pendingExplore.addAll(currentNode.children);
}
}
// Application entry point
public static void main(String[] args) {
TestTree testTree = new TestTree();
testTree.testBFS();
testTree.testDFS();
}
// Node class
public static class Node {
public Node parent;
public List<Node> children = new ArrayList<Node>();
public String nodeName;
public Node(String nodeName) {
this.nodeName = nodeName;
}
public Node createChildNode(String childNodeName) {
Node child = new Node(childNodeName);
child.parent = this;
children.add(child);
return child;
}
}
}
|
