どのDAGもトポロジカルにソートできますか?

私はコンピュータサイエンスでは十分ではありません。私の意図はDAGの点でプログラミングの問題を解決することです。
重要なポイントは、データベースを取得する前に、サイクルがないことを保証するために「トポロジカルソート」を実行する必要があるということです。

Hence, my questions: 1) Does any DAG can be topologically
sorted? Is that a theorem? If yes, what’s a common name for that?
2) Could any non-DAG be topological sorted as well? Can’t I get
into trouble relying only on such a sorting? If
yes, then what is a better way to a) ensure there are no cycles at
all, b) build a proper “string” such that for any pair of verticies
A, B either A < B or B < A?

ベストアンサー

DAG stands for directed acyclic graph.
Therefore no cycles. By applying topological sort you won’t
“uncycle” the cyclic graph
. DAG has no
cycles
. This link may be interesting: https://en.wikipedia.org/wiki/Directed_acyclic_graph#Topological_ordering

トポロジカルな順序の背後にあるアイデアは、ノードiがすべての依存関係の後に置かれるということです。トポロジカルソートを適用すると、親子関係に違反しないオーダーが見つかります。それを大学のコースの要件と考えてください。離散構造(A)と線形代数(B)を実行したときにのみ、AとBが接続されていないアルゴリズムコース(C)を実行する必要があります。だからCはソートされたトポロジカルな順序でAとBの前に現れてはいけません。明らかに、A-B-CおよびB-A-Cは、AまたはBの前にCが遭遇しないので有効な順序である。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です