1. 拓?fù)渑判?/h3>
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]
參考
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))
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 - 鄰接矩陣
