python - 依赖树实现

Question

对于那些使用 apt-get 的人来说，您知道每次安装/卸载某些东西时，您都会收到通知，说明您需要/不再需要某些依赖项。

我正在尝试理解这背后的理论，并可能实现我自己的版本。我做了一些谷歌搜索，想出了大部分耦合的东西。据我了解，耦合是 2 个相互依赖的类/模块。这不是我要找的。我正在寻找的更像是一个依赖树生成，在那里我可以找到最少依赖的模块(我已经做了一个递归的方法)，并且(这是我没有完成的部分)找到什么是删除节点后不再需要。

此外，学习图论会有帮助吗？有没有关于最好使用 Python 作为语言的教程？

Answer 1

图论是必经之路。

图只是一堆位置(顶点)，它们之间有道路(边)，特别是我们谈论的是有向图，这意味着单向道路。基本上，找出依赖关系意味着找出可以沿着单向道路到达特定城镇的所有地点。

现在，您已经拥有了一堆模块，它们成为了您的顶点。假设我们有 A 和 B，并且我们知道 B 依赖于 A，因此存在从 A 到 B 的有向边——“单向路”。

如果 C 依赖于 B，则 A→B→C。

形式上，图只是顶点和(有序的)顶点对的集合，称为边。您想要一种称为“拓扑排序”的图算法，现在您有一些东西要读了。