Topological Sort

Algorithm which finds a linear ordering of a directed acyclic graph where for any edge incident on $u$ and $v$, $u$ comes before $v$.

Note. If a graph has a cycle, then there is no valid ordering! (i.e. suppose $a \rightarrow b \rightarrow a$, then a topological sort must provide an ordering such that $a$ is before $b$ and $b$ is before $a$, but this is impossible)

Note. If a graph has a cycle, then there is no valid ordering! (i.e. suppose $a \rightarrow b \rightarrow a$, then a topological sort must provide an ordering such that $a$ is before $b$ and $b$ is before $a$, but this is impossible)

Topological Sort w/ Depth First Search (**G**):
		initialize **sorted-list**
		
		**while** |**sorted-list**| != number of nodes in **G:**
				select an arbitrary unrecorded node **p** in **G**
				**for** each node **q** adjacent to **p**:
						depth-first search on **q**
						add **q** to **sorted-list**
				add **p** to **sorted-list**
		
		reverse **sorted-list**

Note. This implementation does not require that starting nodes have in-degree 0. This is because post-order DFS already respects the structure of the graph, so, in this example, regardless of whether we chose node $F$ or node $C$ next, the ordering would be maintained.

Note. This implementation does not require that starting nodes have in-degree 0. This is because post-order DFS already respects the structure of the graph, so, in this example, regardless of whether we chose node $F$ or node $C$ next, the ordering would be maintained.

Since $V$ nodes are visited and $E$ edges are considered, the runtime of this algorithm is $\Theta(V + E)$.

Directed Acyclic Graph Shortest Paths

Modification of Dijkstra’s which allows for negative edge weights on a directed acyclic graph.

Recording 2025-04-04 194302.mp4

<aside> đź’ˇ

Directed Acyclic Graph Shortest Paths. Solution which uses a topological sort to apply Dijkstra’s in a linear ordering.

                                  $\\Theta(V  + E )$ *runtime, $\\Theta(V)$ space*

Directed Acyclic Graph Shortest Paths (**G**):
		**fringe** <- topological sort of **G**
		Run **Dijkstra's** on this **fringe**

</aside>

The reason why this works is because it is impossible to find a shorter path between a node and the source if all paths up to that node have already been processed before we reach it.

Trie

Data structure which stores string-valued keys in a tree such that each node contains a letter and every root to marked node path forms a key.

Not shown here. Most of the time, a trie node is marked if the letter it stores corresponds to the last letter in a key.

Not shown here. Most of the time, a trie node is marked if the letter it stores corresponds to the last letter in a key.