[Haskell] 拓扑排序

1. 拓扑排序

import Data.Ix
import Graph

inDegree :: Ix a => Graph a a -> a -> Int
inDegree g n = length [t | v <- nodes g, t <- adjacent g v, n == t]

topologicalSort :: Ix a => Graph a a -> [a]
topologicalSort g = tsort [n | n <- nodes g, inDegree g n == 0] []
    where 
        tsort [] r = r 
        tsort (c:cs) vis | elem c vis = tsort cs vis 
                         | otherwise = tsort cs (c:(tsort (adjacent g c) vis))
                         

2. 用例

testGraph = mkGraph True (1, 6) 
                    [(1, 2, 0), (1, 3, 0), (1, 4, 0),
                     (3, 6, 0), (5, 4, 0), (6, 2, 0),
                     (6, 5, 0)]
                
testTopologicalSort = topologicalSort testGraph
-- [1,3,6,5,4,2]

---

参考

Algorithms: A Functional Programming Approach
Graph - 邻接表
Graph - 邻接矩阵