# On Finding Optimal (Dynamic) Arborescences
## 2 Optimal Arborescences
### Tarjan Algorithm
#### 2.2.4 Illustrative Example  
Let us consider the graph \(G=(V,E)\) in Figure 6. At the beginning of the contraction phase, the forest \(F\) is empty. There is a priority queue associated with each vertex, and the contents are \(Q_{0}=\{(3,0,1)\}\), \(Q_{1}=\{(0,1,6),(2,1,10)\}\), \(Q_{2}=\{(3,2,8),(1,2,10)\}\), and \(Q_{3}=\{(1,3,12)\}\). We have also \(roots=\{0,1,2,3\}\), \(rset=\emptyset\), and \(max[v]=v\) for \(v\in V\). We start popping vertices, denoted by \(r\), from the set \(roots\) and finding the minimum weighted edge incident to each \(r\). We can safely pop zero, one, and two from \(roots\), and the respective minimum weight incident edges \((3,0)\), \((0,1)\), and \((3,2)\), with weights one, six, and eight, respectively, without forming a cycle. These edges are added to forest \(F\) as nodes, thereby leading to the state seen in Figure 7. Since each vertex in \(\{0,1,2\}\) forms a strongly connected component with a single vertex, we have \(\pi[0]=(3,0)\), \(\pi[1]=(0,1)\), and \(\pi[2]=(3,2)\). Figure 6: Input weighted directed graph. Figure 7: Forest \(F\) after popping 0, 1, and 2 from set \(roots\). Note that currently \(roots=\{3\}\), and the contents of each priority queue are \(Q_{0}=\emptyset\), \(Q_{1}=\{(2,1,10)\}\), \(Q_{2}=\{(1,2,10)\}\), and \(Q_{3}=\{(1,3,12)\}\). Vertex \(3\) is then removed from set \(roots\), edge \((1,3)\) is added as a node to \(F\), and \(\pi[3]=(1,3)\). Also, a cycle \(\{(3,0),(0,1),(1,3)\}\) is formed, thereby implying that a contraction must be performed. Let three denote the cycle representant. After the contraction, we have \(max[3]=3\), since \((1,3)\) is the maximum weight edge in the cycle, and we have \(Q_{3}=\{(2,1,16)\}\), \(Q_{2}=\{(1,2,10)\}\), and \(roots=\{3\}\). Figure 8 depicts this first contraction. Vertex \(3\) is yet again removed from the set \(roots\); moreover, edge \((2,1,16)\) is popped out from \(Q_{3}\), and added to \(F\) as a node. Since edge \((2,1,16)\) is incident in a strongly connected component that contains cycle \(C=\{(3,0),(0,1),(1,3)\}\), the edges directed from \((2,1)\) to every edge in \(C\) are created in \(F\), and parent pointers are initialized in the reverse direction, as shown in Figure 9.  
Recall that edge \((3,2)\) was previously selected, and the addition of edge \((2,1)\) forms cycle \(C^{\prime}=\{(2,1),(3,2)\}\). After processing \(C^{\prime}\), let three be the cycle representative, and, hence, \(roots=\{3\}\), \(Q_{3}=\emptyset\), and \(max[3]=3\), since \((2,1)\) is the maximum weight edge in the cycle, and \(\textsc{SFIND(1)}=3\). Finally, three is removed from set \(roots\), but \(Q_{3}\) is empty, thereby ending the contraction phase. The final contracted graph is presented in Figure 10.  
Figure 8: First contraction of the input graph. (**a**) Cycle \(\{(3,0),(0,1),(1,3)\}\) colored in green. (**b**) Contraction result. Figure 10: Last cycle and final contracted graph. (**a**) Cycle \(\{(2,1),(3,2)\}\) marked in green. (**b**) Contraction result. Figure 9: Adding directed edges from node \((2,1)\) to the nodes of cycle \(C\) in forest \(F\). The expansion phase can proceed now. Let \(N=\{(2,1),(3,2)\}\), \(R=\{3\}\), and \(H=\emptyset\). Recall that \(\pi[0]=(3,0)\), \(\pi[1]=(0,1)\), \(\pi[2]=(3,2)\), and \(\pi[3]=(1,3)\). The expansion begins by evaluating the elements from set \(R\), which contain only vertex \(3\). Since \(\pi[3]=(1,3)\), and the path \(P_{3}\) is constructed by following the child-to-parent direction until a root node is found, \(P_{3}=\{(1,3),(2,1)\}\). Then, \(P_{3}\) is removed from \(F\), and the content of set \(N\) is updated to be \(N=\{(3,2),(3,0),(0,1)\}\), as shown in Figure 11.  
Since \(R=\emptyset\), the expansion phase proceeds with an evaluation of the nodes in set \(N\). Set \(N\) is processed similarly to set \(R\) with two minor changes: the elements of \(N\), when removed, are added to \(H\); since \(N\) contains the edges \((u,v)\) as nodes, then the path \(P_{v}\) is traced from the leaf node stored in \(\pi[v]\).