Sunday, 17 April 2011

Graph theory: Strongly-connected components

The F#.NET Journal just published another article about graph algorithms:

"One of the most important fundamental algorithms in graph theory is Tarjan et al.'s 1972 algorithm for computing the strongly-connected components in a graph in linear time. Strongly-connected components are subgraphs where at least one path exists from any vertex to any other vertex. This has many applications and, in particular, is the basis of many more advanced algorithms from graph theory. This article describes both imperative and purely functional implementations of this algorithm and a WPF-based GUI application that visualizes the strongly connected components of a randomly-generated graph..."

To read this article and more, subscribe to The F#.NET Journal today!

No comments: