RIA Shanghai | Adobe上海用户组

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

DFS 广度优先

假设我们要打印各部门收入报表给CEO，因为每个部门收入数据较多，CEO倾向先看各大部门(只有对某部门数据有疑惑时，才看小部门), 这样情况下是先打印大部门，再打印小部门，低等级部门后打印，这就是广度优先的情况。graph的BFS算法较繁琐，但tree的BFS就非常简单了：

visitBFS(a); // visit from the root

// performs BFS from the given node
public void visitBFS(Node nodeStart) {
  List pendingExplore = new ArrayList(); // 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即可。

附：测试程序的完整代码：

import java.util.ArrayList;
import java.util.List;

public class TestTree {
  public Node a;

  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 pendingExplore = new ArrayList(); // 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 children = new ArrayList();

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