Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
The Algorithm Behind the Topological Sort Library TopoSort (github.com/williamw520)
7 points by ww520 on April 3, 2025 | hide | past | favorite | 1 comment
There are some interests on the algorithm behind the Topological Sort Library TopoSort posted a few days ago in finding the dependence free subsets for parallel processing. I've written down the explanation in the linked post.

In essence it is a variant of the Kahn's algorithm. It has sufficient differences that I feel it deserves a separate explanation. It approaches the problem with node sets in a graph instead of individual nodes. This makes the central idea very simple. See the algorithm outline in the write up.






Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: