---
tags: 圖論
title: 拓撲
---

:::success
# 有向無環圖 Directed Acyclic Graph

## 定義

- 不包含有向環的有向圖
- 有拓撲排序
:::

:::info
#### 模板題 [UVa 10305](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1246)
#### [UVa 200](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=136)
:::

:::success
# 拓撲排序

## 定義

- 對有向圖的節點進行排序，使得每一條有向邊$(u,v)$對應的u都在v的前面
- 可能有不止一組合理排序
- 若存在有向環，則不存在拓撲排序(怎麼排都不合理)


- 列舉DFS可能得到的排列：
- case1 : a, b, c -> c應在a前，不合理
- case2 : b, c, a -> a應在b前，不合理
- case3 : c, a, b -> b應在c前，不合理

## 實作

- 用DFS實作
- 利用DFS性質：深度優先 -> $(u,v)$中$u$出現前保證$v$已被訪問過
:::