---
# System prepended metadata

title: 條件相依的排序演算
tags: [程式]

---

### 拓撲排序

- 各套件各有require, 需要先排出讀取順序再逐一讀取.
- 每件工作開始前, 一定需要先完成另一樣工作.
- 假設共有 A,B,C,D
	- A需要B
	- B需要C, D
	- C不相依
	- D需要C
- 需排序為:[C,D,B,A]

### 演算法:
- 卡恩演算法 : 廣度優先, 最終可排出線性排序, 以及造成循環的關係.
- 深度優先搜尋 : 無法直接產生線性排序, 純粹檢測是否有循環關係.

### 參考:
https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
https://www.techiedelight.com/zh-tw/kahn-topological-sort-algorithm/