2008-06-15から1日間の記事一覧

Topological Sort

Topological Sort (トポロジカル ソート): Directed Acyclic Graph(DAG:非循環有向グラフ) G=(V,E)に対し、 全vertexに対する線形順序で、G が edge (u, v) を含んでいれば、線形順序の中で uがvより先に現れる形へのVertex Sort。 Topological-Sort(G) 1…

Depth-First Search

Depth-First Search (深さ優先検索). (Reference:"Introduction to Algorithms, Second Edition") 可能ならば常に"より深く"、グラフを探索する。 未探索の edge(辺) が残されている vertex(頂点) の中で、最後に発見した頂点vのedgeを探索。vのedge全て全…