# 图总结

## 有向无环图

从起点开始，对每个相邻节点dfs，不用考虑标记访问过的节点

[797.所有可能的路径](https://cai-sen-se.gitbook.io/leetcode/601-800/797.-suo-you-ke-neng-de-lu-jing)

## 图遍历dfs模板

```python
def travel(s):	#访问s节点
    #递归出口
    #前序遍历位置
    for neigh in graph[s]:  # 递归访问s的所有相邻节点，graph是邻接表
        travel(neigh)
    #后续遍历位置
```

类似于树的前序和后续遍历，图遍历的dfs也有前序和后序的方式，分别在for语句前后进行操作

### 图的前序遍历

与树的前序类似，先访问当前节点，再访问邻节点

### 图的后序遍历

当前节点的临节点全部访问完毕后，才访问当前节点

## 好友问题

[$277.搜寻名人](https://cai-sen-se.gitbook.io/leetcode/201-400/277.-sou-xun-ming-ren)

[997.找到小镇的法官](https://cai-sen-se.gitbook.io/leetcode/801-1000/997.-zhao-dao-xiao-zhen-de-fa-guan)