> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/28.-reductions-and-decomposition/28.1-topological-sorts-and-dags.md).

# 28.1 Topological Sorts and DAGs

We have covered a tremendous amount of material so far. Programming practices, using an IDE, designing data structures, asymptotic analysis, implementing a ton of different abstract data types (e.g. using a BST, Trie, or HashTable to implement a map, heaps to implement a Priority Queue), and finally algorithms on graphs.

> Why is this knowledge useful?

You may have heard people say that CS 61B teaches much of what you need to solve standard interview questions at tech companies - but why do companies seek candidates with this specific knowledge?

One major reason is that many real world problems can be formulated in such a way that they're solvable with the data structures and algorithms we've learned. This chapter is about working through some tricky problems using the tools we have already learned.

## Topological Sorting <a href="#topological-sorting" id="topological-sorting"></a>

Suppose we have a collection of different tasks or activities, some of which must happen before another. How do we find sort the tasks such that for each task ***v***, the tasks that happen before ***v*** come earlier in our sort?

We can first view our collection of tasks as a graph in which each node represents a task. An edge ***v*****→*****w*** indicates that ***v*** must happen before ***w***. Now our original problem is reduced to finding a **topological sort**.

> **Topological Sort:** an ordering of a graph's vertices such that for every directed edge ***u***→***v***, ***u*** comes before ***v*** in the ordering.

<figure><img src="/files/5Zgsiw7Lo371HKEGjzUU" alt=""><figcaption><p>Question 1</p></figcaption></figure>

<details>

<summary><strong>Question 1.1:</strong> What are some valid topological orderings of the above graph?</summary>

**Answer:** Valid orderings include: \[D,B,A,E,C,F] and \[E,D,C,B,A,F].

</details>

An important note is that it only makes sense to topological sort certain types of graphs. To see this, consider the following graph:

<br>

<figure><img src="/files/3agAjOLF6r2jB5zj6BJl" alt=""><figcaption></figcaption></figure>

<details>

<summary>What is a valid topological sorting of this?</summary>

There isn't one! D comes before B but B comes before C, E, D. Since we have a cycle, topological sort is not defined. We also can't topologically sort an undirected graph since each edge in an undirected graph creates a cycle.

</details>

<br>

<figure><img src="/files/VKQqSZUk1iSeHmVsItRE" alt=""><figcaption></figcaption></figure>

So topological sorts only apply to **directed, acyclic (no cycles) graphs** - or **DAG**s.

> **Topological Sort:** an ordering of a **DAG**'s vertices such that for every directed edge ***u***→***v***, ***u*** comes before ***v*** in the ordering.

For any topological ordering, you can redraw the graph so that the vertices are all in one line. Thus, topological sort is sometimes called a **linearization** of the graph. For example, here's the earlier example linearized for one of the topological orderings.

<br>

<figure><img src="/files/Sdtba0r0WBBhyjvvjpt1" alt=""><figcaption></figcaption></figure>

Notice that the topological sort for the above DAG has to start with either D or E and must end with F or C. For this reason, D and E are called *sources*, and F and C are called *sinks*.

\
[#topological-sorting](#topological-sorting "mention")

How can we find a topological sort? Take a moment to think of existing graph algorithms you already know could be helpful in solving this problem.

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.

**Why it works:** Each vertex ***v*** gets added to the end of the postorder list only after considering **all** descendants of ***v***. Thus, when any ***v*** is added to the postorder list, all its descendants are already on the list. Thus reversing this list gives a topological ordering.

Since we're simply using DFS, the runtime of this is **O(V+E)** where **V** and **E** are the number of nodes and edges in the graph respectively.

#### Pseudocode <a href="#pseudocode" id="pseudocode"></a>

```
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)
```

<details>

<summary><strong>(Out of scope) Extra question:</strong> How could we implement topological sort using BFS? <em>Hint 1: We'd definitely need to store some extra information.</em> <em>Hint 2: Think about keeping track of the in-degrees of each vertex.</em></summary>

**Solution:**

1. Calculate in-degree of all vertices.
2. Pick any vertex �v which has in-degree of 0.
3. Add �v to our topological sort list. Remove the vertex �v and all edges coming out of it. Decrement in-degrees of all neighbors of vertex �v by 1.
4. Repeat steps 2 and 3 until all vertices are removed.

How can we accomplish Step 2 efficiently? We can use a min Priority Queue of vertices with priority equal to the in-degrees.

</details>

### Review <a href="#review" id="review"></a>

* Topological sorts are a way of linearizing **Directed, Acyclic Graphs (DAGs)**.
* We can find a topological sort of any DAG in **O(V+E)** time using **DFS** (or **BFS**).