Hacker News new | ask | show | jobs
by LawnboyMax 2729 days ago
I guess it's also worth mentioning strongly connected components (SCCs) in this context (i.e. there is a directed path from any node to any other node in a component).

In the context of data analytics a SCC finding algo can be used to identify bottlenecks of communication/transportation networks and fault tolerance of distributed networks. In this case we are particularly interested in edges that connect SCCs. Another application is clustering. For instance, finding clusters of accounts that all follow each other on Twitter. In this case each such cluster is a SCC.

Kosaraju–Sharir algorithm is an easy to understand SCC algorithm with linear running time that basically consists of two BFS passes.

P.S. NetworkX (https://networkx.github.io/) is a great Python library for working with graphs. It has implementations of many common graph algos including SCC finding algorithm (it is an implementation of Tarjan's algorithm).