有向图路径可达性与状态压缩计数
有向图的邻接矩阵其实挺常见的，不过当你开始玩深一点，比如求传递闭包或者路径可达性时，A+和A*这两个概念就派上用场了。A+就是基础的传递闭包，告诉你哪些点能直接或间接走到；A*在它基础上再加点料，把自己到自己的可达性也考虑进来了——对角线全是 1，蛮实用的。
状态压缩的拓扑序列计数也是挺有意思的一种玩法。嗯，简单说就是把所有节点的访问状态打包成一个整数，配合动态规划，可以大大减少内存和计算量，适合点数不太多（比如 20 以下）的有向图。
推荐你去看看这篇《基于状态压缩的有向图拓扑序列计数》，讲得比较清楚，代码也挺直白的。用 Java 写的，但逻辑和思路换成 JS 或 Python 也没啥问题。
如果你刚好在搞图的可达性判断、路径搜索优化，或者需要稀疏图中的路径组合问题，可以参考下 A+ 和 A* 的差别，也可以顺手试试状态压缩做法，响应快，效率高。
文件大小：4.19MB
评论区