2 ms·
Tarjan's strongly connected components algorithm. It finds strongly connected components in a graph (read: cyclic dependencies), while doing a topological sort
by zamalek 8y ago
Tarjan's strongly connected components algorithm.
It finds strongly connected components in a graph (read: cyclic dependencies), while doing a topological sort (read: you could use it for a package manager to determine which packages to install first).
It is proof of a very deep understanding of the nature of graphs.
Edit: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_...
- war1025 8y agoAt my work, we have a simulation system that uses Tarjan's algorithm to determine the order that update's need to be applied in order to properly propagate to all downstream nodes. Thought it was pretty neat when I realized our connected components code could do that for us.