トポロジカル順序付けは有向無閉路グラフ(directed acyclic graph)について定義されるものである。閉路がない有向グラフだと必ず順番のようなものを付けることができる。具体的にどういうものに使えるか、というと 仕事の順番 服を着る順番 講義科目の履修順…

有向グラフにおける連結成分の集合みたいなのがどうだったか忘れたので、無向グラフ化(両方を有向にするっぽい感じで)して考えることにした。 # -*- coding: utf-8 -*- require 'pp' require 'set' class Graph def initialize(edges) @edges = edges @nodes…

バックトラックとかしなくていいので、結構簡単にできた。 # -*- coding: utf-8 -*- require 'pp' class Graph def initialize(edges) @edges = edges @nodes = Hash.new{|h,k| h[k] = []} end def add_edge(edge) @edges.push edge unless @edges.index(edg…

index グラフの勉強だけじゃなくてRubyの勉強にもなりそうなソースだなーと思ったので、メモしておく。ファイルは2つとなっていて把握しやすい。 graph.rb graph_algorithm.rb graph.rb module Graphとclass DirectedHashGraph、DirectedHashGraphを拡張した…