トポロジカルソート
Sign in to saveAlso known as topological ordering, topological sort
an ordering of the vertices of the directed graph for which each edge is directed from earlier to later in the ordering
Wikidata facts
- Instance of
- computational problem
- Subclass of
- sorting
Show 3 more facts
- facet of
- directed acyclic graph
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · 日本語
トポロジカルソート（英: topological sort）は、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。 有向非巡回グラフのノードの集合に到達可能性関係 R (ノード x から y への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り xRy とする)を定めると、R は半順序関係となる。トポロジカルソートとは、この R を全順序になるように拡張したものとみなせる。
Abstract from DBpedia / Wikipedia · CC BY-SA