按照教科书的顺序来说,搜索相关的问题应该放在图的章节。 但实际上这部分内容在树的遍历已经涉及,只是DFS和BFS是更通用的情况。 首先不管是inorder、preorder还是postorder traversal,都是一种DFS,只是在图的一种特殊形式二叉搜索树上的一种特殊表现。 讲了这么多,那么DFS的形式到底应该是什么样的呢?或者说具体到代码上又是怎样体现的呢?
DFS的典型实现 一般来说,在以往的教材里我们都被教育DFS的实现都需要一个栈的数据结构,除此之外还需要一个额外的数据结构来记录已经访问的节点。 好吧,废话少说,上代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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); doProcess(node) ArrayList<Node> adjacentNodes = getUnvistedAdjacentNodes(node, visited); for (Node nodeItem : adjacentNodes) { stack.push(nodeItem); } } }
上面是java版本,python呢,算法结构是一样的,不一样的是python下需要用list来实现stack。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def _dfs (): stack = [] visited = set () stack.append(self.root) visited.add(self.root) while stack: node = stack.pop() visited.add(node) do_process(node) adjacent_nodes = generate_unvisited_adjacent_nodes(node, visited) stack.extend(adjacent_nodes)
BFS的典型实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 音)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def _dfs (): queue = deque() visited = set () queue.append(self.root) visited.add(self.root) while stack: node = queue.popleft() visited.add(node) 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。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 private void _wfs () { PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>(); 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.
1 2 3 4 5 6 7 class Node implements Compareable <Node > { ...... @Override public int compareTo (Node o) { return o.data - data; } }
类似的,python的实现需要解决PriorityQueue的实现问题,很幸运,PriorityQueue在collection下有实现,那么具体的WFS实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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测试工程