# 图论

## 最短/最长路径计算方法

其中$$w$$指边的权重

|                              |                                                                                                                                                                                                                                                                                                                       |                                                                                             |
| ---------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------- |
| 图的类型                         | 最短路径                                                                                                                                                                                                                                                                                                                  | 最长路径                                                                                        |
| *DAG* ($$w \in \mathbb{R}$$) | [DP(Toposort)](https://maomaoalgo.gitbook.io/python/tu-de-xing-zhi/you-xiang-tu-de-zui-zhi)                                                                                                                                                                                                                           | [DP(Toposort)](https://maomaoalgo.gitbook.io/python/tu-de-xing-zhi/you-xiang-tu-de-zui-zhi) |
| 一般有向/无向图                     | <p><span class="math">w = \text{const}</span>: <a href="wu-xiang-tu-de-zui-zhi#wu-quan-tu-zui-duan-lu-jing">BST</a></p><p><span class="math">w \in \mathbb{R}^+</span>: <a href="wu-xiang-tu-de-zui-zhi#jia-quan-tu-zui-duan-lu-jing">Dijkstra</a></p><p><span class="math">w \in \mathbb{R}</span>: Bellman-Ford</p> | NP-hard([具体证明](https://en.wikipedia.org/wiki/Longest_path_problem#NP-hardness))             |

## 环的检测

|      |                                                                                                                                                                                                        |
| ---- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |
| 图的类型 | 方法                                                                                                                                                                                                     |
| 无向图  | <p><a href="huan-de-jian-ce#unionfind-yan-zheng-wu-xiang-tu-de-wu-huan-xing">UF</a>：动态方法</p><p><a href="huan-de-jian-ce#shen-du-you-xian-sou-suo-yan-zheng-wu-xiang-tu-de-wu-huan-xing">DFS</a>：遍历</p> |
| 有向图  | <p><a href="huan-de-jian-ce#tuo-pu-pai-xu-yan-zheng-dag-de-wu-huan-xing">BFS</a>：拓扑排序</p><p><a href="huan-de-jian-ce#shen-du-you-xian-sou-suo-yan-zheng-dag-de-wu-huan-xing">DFS</a>：染色法</p>           |

## 连通分量计算方法（未完成）

|      |            |                                           |
| ---- | ---------- | ----------------------------------------- |
| 图的类型 | 连通分量       | 计算方法                                      |
| 无向图  |            | <p>UF：动态方法</p><p>DFS：遍历</p>               |
| 有向图  | SCC（强连通分量） | <p>Toposort+DFS</p><p>（计算后的SCC是一个DAG）</p> |