> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/graph-and-search.md).

# Graph and  Search

克隆图

先点后边，hashmap 建立旧点新点映射

拓扑排序

有向图不能用DFS 因为多个点指向一个点，会不断回溯

树BFS vs 图BFS

看是否有左右子树， 图是否有neighbor for 循环

宽度优先搜索不会回溯，每个点只遍历一遍

```
private String replace(String s, int index, char c) {
        char[] chars = s.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
```

遍历模板

````
```python
directions = [(1,0),(0,1),(-1,0),(0,-1)]
        for dx,dy in directions:
            nx,ny = x+dx,y+dy
            if 0<=nx<n and 0<=ny<=m and grid[nx][ny] == 1:
                uf.union(ny,ny)
```
````