> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/basic_graph_algorithms/topological_sorting.md).

# Topological Sort

* A topological ordering of a graph is an ordering of all the vertecies in a graph such that if node A -> B, then A will come before B in the ordering.
* We can think of the edges as B depends on A. So in order to get to node B, we must get through node A.
* If a graph is a DAG, it has topological ordering, and if a graph has topological ordering, it is also a DAG.

## Constraints

* A graph must be a DAG (directed acyclic graph) for topological sorting to be possible.
  * Why:
    * If non-directed, then A <--> B for all nodes, so there is no ordering possible.
    * Acyclic because if a cycle does exist, then then that means there exist at least one cycle in the graph where all the nodes depend on each other (which do we chose first?).

## Algorithm

1. Select node S that has no incoming edges, and push into some set.
2. Remove node S from graph (and its connections)
3. See 1.

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI0gGotAzJGi-H75d%2Fdag_top_ordering.png?generation=1568003605755775\&alt=media)

```
5
a->b
a->c
a->d
a->e
b->d
c->d
c->e
d->e
```