深度优先搜索（DFS：Depth First Search）、广度优先搜索（BFS： Breadth First Search）与启发式搜索（Heuristic Search）

文章目录

1. DFS的典型实现
2. BFS的典型实现
3. WFS (Weight First Search)

按照教科书的顺序来说，搜索相关的问题应该放在图的章节。
但实际上这部分内容在树的遍历已经涉及，只是DFS和BFS是更通用的情况。
首先不管是inorder、preorder还是postorder traversal，都是一种DFS，只是在图的一种特殊形式二叉搜索树上的一种特殊表现。
讲了这么多，那么DFS的形式到底应该是什么样的呢？或者说具体到代码上又是怎样体现的呢？

DFS的典型实现

一般来说，在以往的教材里我们都被教育DFS的实现都需要一个栈的数据结构，除此之外还需要一个额外的数据结构来记录已经访问的节点。
好吧，废话少说，上代码。

private void _dfs() {
       Stack<Node> stack = new Stack<Node>();
       Set<Node> visited = new HashSet<Node>();
       stack.push(this.root);
       while (!stack.isEmpty()) {
           Node node = stack.pop();
           visited.add(node);
           // do something process
           doProcess(node)

           ArrayList<Node> adjacentNodes = getUnvistedAdjacentNodes(node, visited);
           for (Node nodeItem : adjacentNodes) {
             stack.push(nodeItem);
           }
       }
   }

上面是java版本，python呢，算法结构是一样的，不一样的是python下需要用list来实现stack。

def _dfs():
    stack = []
    visited = set()
    stack.append(self.root)
    visited.add(self.root)
    while stack:
        node = stack.pop()
        visited.add(node)

        # do something
        do_process(node)

        adjacent_nodes = generate_unvisited_adjacent_nodes(node, visited)
        stack.extend(adjacent_nodes)

BFS的典型实现

private void _bfs() {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<Node>();
    queue.offer(this.root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        visited.add(node);
        doProcess(node)

        ArrayList<Node> adjacentNodes = getUnvistedAdjacentNodes(node, visited);
        for (Node nodeItem : adjacentNodes) {
          queue.offer(nodeItem);
        }
    }
}

同样，python版本需要解决Queue的实现，这里需要用到双端队列deque（注意这个单词发 deck 音）

def _dfs():
    queue = deque()
    visited = set()
    queue.append(self.root)
    visited.add(self.root)
    while stack:
        node = queue.popleft()
        visited.add(node)

        # do something
        do_process(node)

        adjacent_nodes = generate_unvisited_adjacent_nodes(node, visited)
        queue.extend(adjacent_nodes)

WFS (Weight First Search)

这是什么鬼？教科书里没有啊。
是的，这是我根据启发式搜索（Heuristic Search）写出的一个自定义搜索方式。
要想说清楚 WFS 就要先搞清楚启发式搜索，要想说清启发式搜索又要看看 DFS 和 BFS 的算法。
我们注意到 DFS 和 BFS 算法在只是在使用的数据结构上有所不同，DFS 使用的是Stack， BFS 使用的是Queue，而我们知道在PriorityQueue的前提下，Stack和Queue是可以统一的，如果这里的数据结构换成ProrityQueue就变成了启发式搜索（Heuristic Search）。
下面说WFS，这里如果PriorityQueue的估价函数是关于权重的话，那么这个搜索就是WFS。

private void _wfs() {
    PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
//        PriorityQueue<TreeNode> priorityQueue = new PriorityQueue<TreeNode>((a,b) -> b.data - a.data);
    Set<Node> visited = new HashSet<>();
    priorityQueue.add(this.root);
    while (!priorityQueue.isEmpty()) {
        Node node = priorityQueue.poll();
        visited.add(node);
        doProcess(node);

        ArrayList<Node> adjacentNodes = getUnvistedAdjacentNodes(node, visited);
        for (Node nodeItem : adjacentNodes) {
          queue.offer(nodeItem);
        }
    }
}

当然这里Node需要实现 Compareable interface.

class Node implements Compareable<Node>{
  ......
  @Override
  public int compareTo(Node o) {
    return o.data - data;
  }
}

类似的，python的实现需要解决PriorityQueue的实现问题，很幸运，PriorityQueue在collection下有实现，那么具体的WFS实现如下：

def wfs(self):
    priority_queue = PriorityQueue()
    visited = set()
    priority_queue.put(self.root)

    while not priority_queue.empty():
        node = priority_queue.get()
        do_process(node)

        adjacent_nodes = generate_unvisited_adjacent_nodes(node, visited)
        queue.extend(adjacent_nodes)
```  

类似的Node需要重写 _cmp_ 方法

``` python
class Node(object):
    ......

    def __cmp__(self, other):
        return other.val - self.val

对应的这三种搜索实现在BST下都有具体的工程实现，实现参考github工程的java实现 — python实现
和对应的java测试工程