Content deleted Content added
Citation bot (talk | contribs) m Alter: template type. Add: date, year, doi. Removed URL that duplicated unique identifier. Removed accessdate with no specified URL. | You can use this bot yourself. Report bugs here.| Activated by User:Headbomb |
|||
Line 97:
While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse [[Topological sorting|topological sort]] of the [[Directed acyclic graph|DAG]] formed by the strongly connected components.<ref>{{cite web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|accessdate=9 February 2011}}</ref>
[[Donald Knuth]] described Tarjan's algorithm as one of
He also wrote:<ref>{{cite book|last=Knuth|first=Donald|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions|date=2014-05-20}}</ref> {{quote|The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct.}}
| |||