トポロジカルソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/27 01:22 UTC 版)
トポロジカルソート（英: topological sort）は、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。
- ^ Jarnagin, M. P. (1960). Automatic machine methods of testing PERT networks for consistency. Technical Memorandum No. K-24/60. Dahlgren, Virginia: U. S. Naval Weapons Laboratory.
- ^ Kahn, A. B. (1962). “Topological sorting of large networks”. Communications of the ACM 5 (11): 558–562. doi:10.1145/368996.369025.
- ^ T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン（日本語） 『アルゴリズムイントロダクション』（第3版）近代科学社、2013年12月17日 （原著2009-7-31）。ISBN 476490408X。
- ^ Tarjan, Robert E. (1976). “Edge-disjoint spanning trees and depth-first search”. Algorithmica 6 (2): 171–185. doi:10.1007/BF00268499.
- ^ Vernet, Oswaldo; Markenzon, Lilian (1997). “Hamiltonian problems for reducible flowgraphs”. Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97). pp. 264–267. doi:10.1109/SCCC.1997.637099.
[続きの解説]
「トポロジカルソート」の続きの解説一覧
- 1 トポロジカルソートとは
- 2 トポロジカルソートの概要
- 3 関連項目
- トポロジカルソートのページへのリンク
