Directed graphs¶
 Acyclic graphs($\text{DAGs}$): There are no cycles in the graph, so there is no path from any node to itself.
 Successor graphs: The out degree of each node is 1, so each node has a unique successor.
Topological sorting¶
A Topological sort is an ordering of the nodes of a directed graph such that if there is a path from node $a$ to node $b$, then node $a$ appears before node $b$ in the ordering.
An acyclic graph always has a topological sort.
Note
It turns out that depthfirst search($\text{DFS}$) can be used to both check if a directed graph contains a cycle and, if it does not contain a cycle, to construct a topological sort.
Implementation(Using DFS)¶
The idea is to go through the nodes of the graph and always begin a depthfirst search at the current node if it has not been processed yet. during the the searches the node have three possible states:
 state 0: the node has not been processed
 state 1: the node is under processing
 state 2: the node has been processed
Initially, the state of each node is 0. When a search reaches a node for the first time, its state becomes1. Finally, after all successors of the node have been processed, its state becomes 2.
If the graph contains a cycle, we will find this out during the search, because sooner or later we wil arrive at a node whose state is 1. In this case, it is not possible to construct a topological sort.
If the graph does not contain a cycle, we can construct a topological sort by adding each node to a list when the state of the node becomes 2. This list in reverse order is topological sort.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 

Related Problems¶
Dynamic Programming¶
If a directed graph is acyclic, dynamic programming can be applied to it. For example, we can efficiently solve the following problems concerning paths from a starting node to and ending node
1. Counting the number of paths¶
Let
paths(x)
denote the number of paths from node $1$ to node $x$. As a basecase,paths(1)
1. Then to calculate other values ofpaths(x)
, we may use recursion
1 

where a1, a2, ..., ak are the nodes from which there is an edge to x.
Since the graph is acyclic the values of
paths(x)
can be calculated in the order of topological sort.
2. Extending Dijkstra's algorithm¶
A byproduct of Dijkstra's algorithm is a directed, acyclic graph that indicates for each node of the original graph the possible ways to reach the node using a shortest path from the starting node. Dynamic programming can be applied to that graph.
thus we can find number of shortest paths from node $a$ to node $b$
3. Representing problems as graphs¶
Actually, any dynamic programming problem can be represented as a directed acyclic graph. In such a graph, each node coressponds to a dynamic programming state and the edges indicate how the states depend on each other.
Successor paths¶
Successor graphs: the outdegree of each node is 1.
A successor graph consists of one or more components, each of which contains one cycle and some paths that lead to it.
Successor graphs are sometimes called functional graphs. The reason for that is that any successor graph corresponds to a function that defines the edges of the graph.
The parameter of the function is a node of the graph, and the function gives the successor of that node.
succ(x, k)
¶
Since each node of a successor graph has a unique successor, we can also define a function
succ(x, k)
that gives the node that we will reach if we begin at nodex
andk
step forward.Using preprocessing, any value of
succ(x, k)
can be calculated only $\Omicron(lgk)$ time.The idea is to precalculate all values of
succ(x, k)
wherek
is a power of two and at mostu
, where u is the maximum number of steps we will ever walk.This can be efficiently done, because we can use the following recursion
1 2 3 4 5 6 

Precalculating the values takes $\Omicron(nlgu)$ time because $\Omicron(lgu)$ values are calculated for each node.
After precalculating, any value of
succ(x, k)
can be calculating presenting the number of steps k as a sum of pwoers of two.
$$ succ(x, 11) = succ(succ(succ(x, 8), 2), 1); $$
Such a representation always consists of $\Omicron(lgk)$ parts, so calculating a value of
succ(x, k)
takes $\Omicron(lgk)$ time.
Cycle Detection¶
Consider a successor graph that only contains a path that ends in a cycle. A simple way to detect the cycle is to walk in the graph and keep track of all nodes that have been visited. Once a node is visited for the second time we can conclude that the node is the first node in the cycle. This method works in $\Omicron(n)$ time and also uses $\Omciron(n)$ memory.
There are better algorithms for cycle detection. The time complexity of such algorithm is still $\Omicron(n)$, but they only use $\Omicron(1)$ memory. This is an important improvement if $n$ is large.
Floyd's algorithm¶
Floyd's algorithm walks forward in the graph using two pointers $a$ and $b$. Both pointers begin at node $x$ that is the starting node of the graph. Then on each turn, the pointer $a$ walks one step forward and the pointer $b$ walks to steps forward. The process continues until the pointer meet each other.
1 2 3 4 5 6 

At this point, the pointer $a$ has walked $k$ steps and the pointer $b$ has walked $2k$ steps, so the length of the cycle divides $k$. Thus, the first node that belongs to the cycle can be found by moving the pointer $a$ to node $x$ and advancing the pointers step by step until they meet again.
1 2 3 4 5 6 

After this, the length of the cycle can be calculated as follows
1 2 3 4 5 6 
