# Tips

## DFS

#### recursion

in n-tree, or graph 

```python
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

```python
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)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MeIkJgUOie5y4gfq9UA%2F-MeIkWMvJ8lOgFj0crbF%2Fimage.png?alt=media\&token=00165aff-21b3-48ea-b817-1d09b9d67e58)

```
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\[] 或是改變值