<p>DAG stands for directed <strong>acyclic</strong> graph. Therefore no cycles. By applying topological sort you <strong>won't "uncycle" the cyclic graph</strong>. DAG has <strong>no cycles</strong>. This link may be interesting: <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph#Topological_ordering" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Directed_acyclic_graph#Topological_ordering</a></p>

<p>The idea behind topological order is that node i is placed after all of it's dependencies. By applying topological sort you find an order, which doesn't violate parent/child dependency. Think of it as requirements to a course at university. You should do algorithms course (C), only when you've done discrete structures(A) and linear algebra (B), whereby A and B are not connected. So C should not appear before A and B in the sorted topological order. Obviously A-B-C and B-A-C is a valid order, since C is not encountered before A or B.</p>

CC BY-SA 3.0
2018-02-11T10:58:01.070Z
2018-02-11T10:58:01.070Z
denis631
<p>I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. <strong>The key point</strong> is that before getting them into database, I need run "topological sort" in order to guarantee an absence of cycles. </p>

<p>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 <strong>only</strong> 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 &lt; B or B &lt; A?</p>

CC BY-SA 3.0
2018-02-10T14:25:59.047Z
Any DAG with no cycle can be sorted according to the topological sorting algorithm.
user529767
CC BY-SA 3.0
2018-02-11T11:55:51.190Z
Do you mean to ask what would happen if one runs a topological sort on a directed graph _with_ cycles?  If so, please edit the question.
András Salamon
<graph-theory><sorting><topological-graph-theory>
Does any DAG can be topologically sorted?
Zazaeil
# Does any DAG can be topologically sorted?

(Asked by: username_0 on 2018-02-10)

I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. **The key point** is that before getting them into database, I need run "topological sort" in order to guarantee an absence of cycles.

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?

**Tags:** graph-theory, sorting, topological-graph-theory
> **Comments:**
> **username_1**: Any DAG with no cycle can be sorted according to the topological sorting algorithm.  
> **username_2**: Do you mean to ask what would happen if one runs a topological sort on a directed graph _with_ cycles?  If so, please edit the question.  

---

## 1 answers

### Answer by username_3 on 2018-02-11. Score: 0 | Accepted answer

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>

The idea behind topological order is that node i is placed after all of it's dependencies. By applying topological sort you find an order, which doesn't violate parent/child dependency. Think of it as requirements to a course at university. You should do algorithms course (C), only when you've done discrete structures(A) and linear algebra (B), whereby A and B are not connected. So C should not appear before A and B in the sorted topological order. Obviously A-B-C and B-A-C is a valid order, since C is not encountered before A or B.


---

