2009-07-07から1日間の記事一覧

有向グラフを強連結成分に分解するアルゴリズム

CormenのIntroduction to Algorithmsには,グラフGと有向辺を逆にしたG_revに対してそれぞれDFSする方法が紹介されている.これは,わかりやすいアルゴリズムではあるのだけれど,逆グラフを求める必要があるのが玉にキズである.一方,SedgewickのAlgorithm…