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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/graph-and-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.