読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

トポロジカルソートをWikipediaを参考にRubyで書いてみた。
トポロジカルソートとは、(これも名前がいけてない気がするが・・・)、DAGを左から右に進むように一列に並べること。一意ではないが、存在は示せる。
数学的には、DAG(半順序)を拡張し、すべての頂点同士を比較可能(全順序)にしたもの、と言えるらしい。なるほど、ということは配列に埋め込めれば全順序なのか。
料理などで、野菜を切った後にお肉を炒めて、・・・、スープを作って、野菜をスープに入れて、・・・、アクを取って、・・・みたいなのはある種トポロジカルソートしてるんだね。つーか、すべての料理本では既に手順がトポロジカルソートされて(+有向辺の情報が削除)いるのだった。DAGで手順を書いた料理本を出せば流行るかもしれない。Cookpadで採用しないかなあ。


2つのアルゴリズムがあって、深さ優先探索をするのと、各辺の辺が入ってくる数と辺が全く入ってこない頂点集合を管理する方法。
どういう順番で深さ優先するか、頂点集合からpopするときの順番などでそれぞれ返り値が異なってくる。

class Graph
	def initialize(n)
		@n=n #num of vertex
		@e=Array.new(n){Array.new}
	end
	
	def add(v,w)
		@e[v].push(w)
		#@e[w].push(v)
		self
	end
	
	def tsort_kahn
		ret=[]
		s=[]
		in_num=Array.new(@n,0)
		@e.each{|ary|ary.each{|w|in_num[w]+=1}}
		in_num.each_with_index{|num,v|s.push(v) if num==0}
		until s.empty?
			v=s.pop
			ret.push(v)
			@e[v].each{|w|in_num[w]-=1;s.push(w) if in_num[w]==0}
		end
		ret
	end
	
	def tsort_tarjan
		@ret=[]
		@explored=Array.new(@n,false)
		def visit(v)
			unless @explored[v]
				@explored[v]=true
				@e[v].each{|w|visit(w)}
				@ret.push(v)
			end
		end
		
		@n.times{|v|visit(v)}
		@ret.reverse
	end
end

g=Graph.new(9)
[[0,1],[0,2],[1,5],[1,7],[2,3],[2,4],[2,8],[3,5],[4,5],[4,6],
[5,7],[6,7],[6,8],[7,8]].each{|v,w|g.add(v,w)}

p g.tsort_tarjan