依赖树实现

本文介绍了依赖树实现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

For those who used apt-get, you know that everytime you install / uninstall something, you get the notificatons saying you need / no longer need certain dependencies.

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

I'm trying to understand the theory behinds this and potentially implement my own version of this. I've done some googling, came up with mostly coupling stuff. From what I understand, coupling is 2 classes/modules that depends on each other. This is not exactly what I'm looking for. What I'm looking for is more like a dependencies tree generation, where I can find the least dependent module (I've already made a recursive way of doing this), and (this being the part i haven't done) finding what's no longer needed after removing a node.

另外，了解图论会有所帮助吗？

Also, would learning about graph theory help? And is there any tutorials on that preferably using Python as a language?

推荐答案

图论是解决之道。

图形只是一堆地方（顶点），它们之间有道路（边），尤其是我们所说的有向图，即单向道路。找出依赖关系，基本上意味着找出沿单向道路可以到达特定城镇的所有地点。

A graph is just a bunch of places (vertices) with roads (edges) between them, and in particular we're talking about a directed graph, which means one-way roads. Figuring out dependencies means, basically, finding out all the places that can reach a particular town along the one-way roads.

因此，现在，您有了很多模块，它们成为您的顶点。假设我们有A和B，并且我们知道B取决于A，所以存在从A到B的定向边缘-单向道路。

So now, you've got you bunch of modules, which become your vertices. Let's say we have A and B, and we know B depends on A, so there's a directed edge -- a "one way road" -- from A to B.

如果C依赖于B，那么您就有A→ B→ C。

If C depends on B, then you have A→B→C.

形式上，图只是一个顶点和（有序）顶点对的集合，称为边缘。您需要一种称为拓扑排序的图算法，现在您已经掌握了一些知识。

Formally, a graph is just a collection of vertices and (ordered) pairs of vertices, called the edges. You want an graph algorithm called "topological sort", and now you've got some stuff to read.