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

按照教科书的顺序来说,搜索相关的问题应该放在图的章节。
但实际上这部分内容在树的遍历已经涉及,只是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);
// do something process
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 something
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 something
do_process(node)

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

这是什么鬼?教科书里没有啊。
是的,这是我根据启发式搜索(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
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.

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测试工程

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