Tips

DFS

recursion

in n-tree, or graph

visited = set() 

def dfs(node, visited):
    if node in visited: # terminator
    	# already visited 
    	return 

	visited.add(node) 

	# process current node here. 
	...
	for next_node in node.children(): 
		if next_node not in visited: 
			dfs(next_node, visited)

use stack

def DFS(self, tree): 

	if tree.root is None: 
		return [] 

	visited, stack = [], [tree.root]

	while stack: 
		node = stack.pop() 
		visited.add(node)

		process (node) 
		nodes = generate_related_nodes(node) 
		stack.push(nodes) 

	# other processing work 
	...

BFS

time: O(V+E)

def BFS(graph, start, end):
    visited = set()
	queue = [] 
	queue.append([start]) 

	while queue: 
		node = queue.pop() 
		visited.add(node)

		process(node) 
		nodes = generate_related_nodes(node) 
		queue.push(nodes)

	# other processing work 
	...

注意: 102, 127 example

qSize 一定要提出來, 不然會錯(why...?

        int qSize = queue.size();
        for (int q = 0; q < qSize; q++) {

127 word ladder, 一開始記得要移掉 beginWord

wordlist 要轉成 set

set.remove(beginWord);

原始做法用 visited[] 來記錄走過的, 但像 flood fill, 是會去把走過的值改掉, 代表走過了, 所以不用 visited[], 看狀況使用 visited[] 或是改變值