Topological Sort(拓撲排序)
學習資源
- 選手村的書裡
- 演算法筆記
找出一個合理的排列順序（ Kahn's Algorithm ）
變數 adj 代表 "adjacency matrix"（鄰接矩陣）的縮寫。
python
def topological_ordering():
for i in range(9):
ref[i] = 0 # 初始化為0
# 累計圖上每一個點被幾條邊連到
for i in range(9):
for j in range(9):
if adj[i][j]:
ref[j] += 1
# 開始找出一個合理的排列順序
for i in range(9):
# 尋找沒有被任何邊連向的點
s = 0
while s < 9 and ref[s] != 0:
s += 1
if s == 9:
break # 找不到。表示目前殘存的圖是個環。
ref[s] = -1 # 設為已找過（刪去s點）
print(s, end=" ") # 印出合理的排列順序的第i點
# 更新ref的值（刪去由s點連出去的邊）
for t in range(9):
if adj[s][t]:
ref[t] -= 1
adj = [[False] * 9 for _ in range(9)] # adjacency matrix
ref = [0] * 9 # 記錄圖上每一個點目前仍被多少條邊連到
topological_ordering()Contributors
lucashsu95