> For the complete documentation index, see [llms.txt](https://xiaoyang-liu.gitbook.io/programming-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiaoyang-liu.gitbook.io/programming-notes/computer-science/data-structures/reductions-and-decomposition.md).

# Reductions and Decomposition

## Topological Sort

* Topological Sort is an ordering of a graph's vertices such that for every directed edge u→v, u comes beforev in the ordering.
* Topological sorts only apply to directed, acyclic (no cycles) graphs (DAG).
* Topological sort is called a linearization of the graph, since all the vertices in the graph could be redrawn in one line.

### Topological Sort Algorithm

* Perform a DFS traversal from every vertex in the graph, not clearing markings in between traversals.
* Record DFS postorder along the way.
* Topological ordering is the reverse of the postorder.

The total runtime of DFS is `O(V + E)`.

```
topological(DAG):
    initialize marked array
    initialize postOrder list
    for all vertices in DAG:
        if vertex is not marked:
            dfs(vertex, marked, postOrder)
    return postOrder reversed

dfs(vertex, marked, postOrder):
    marked[vertex] = true
    for neighbor of vertex:
        dfs(neighbor, marked, postOrder)
    postOrder.add(vertex)
```

## Shortest Path Algorithm for DAGs

* Visit vertices in topological order.
* On each visit, relax all outgoing edges.