Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 105
Текст из файла (страница 105)
A directed edge (u, v) in thedag of Figure 22.7(a) indicates that garment u must be donned before garment v. Atopological sort of this dag therefore gives an order for getting dressed. Figure 22.7(b) showsthe topologically sorted dag as an ordering of vertices along a horizontal line such that alldirected edges go from left to right.Figure 22.7: (a) Professor Bumstead topologically sorts his clothing when getting dressed.Each directed edge (u, v) means that garment u must be put on before garment v.
Thediscovery and finishing times from a depth-first search are shown next to each vertex. (b) Thesame graph shown topologically sorted. Its vertices are arranged from left to right in order ofdecreasing finishing time. Note that all directed edges go from left to right.The following simple algorithm topologically sorts a dag.TOPOLOGICAL-SORT(G)1 call DFS(G) to compute finishing times f[v] for each vertex v2 as each vertex is finished, insert it onto the front<b>Текст обрезан, так как является слишком большим</b>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
