算法-搜索

Posted on | In |

BFS代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BFS(graph, start, end)

	queue = []
	queue.append([start])
	visited.add(start)

	while queue:
		node = queue.pop()
		visited.add(node)
	
		process(node)
		nodes = generate_related_node(node)
		queue.push(nodes)
		
	# other processing work
	...

DFS

递归写法

1
2
3
4
5
6
7
8
visited = set()
dfs(node, visited)
	visited.add(node)
	#process current node here
	...
	for next_node in node.children():
		if not next_node in visited:
			dfs(next_node, visited)

非递归写法（不常用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DFS(self, tree)
	if tree.root is None
		return []
	visited, stack = [], [tree.root]
	
	while stack:
		node = stack.pop()
		visited.add(node)
		
		process(node)
		node = generate_related_nodes(node)
		stack.push(nodes)
	
	# other processing work
	...