algorithm - 我应该使用迭代加深深度优先搜索 (IDDFS) 迭代有向图吗？

Question

示例:我有 20 个人作为对象，每个人都认识 0-n 个人。链接的方向很重要! A 可能认识 B，但 B 可能不认识 A。这是一个有向图。

编辑: 为了简化，我的节点对象(在本例中为 Person 对象)能够存储任意信息。我知道这不是最好的设计，但现在这样就可以了。

所以在最坏的情况下，每个人都与其他人联系在一起，每个人都认识其他人。这不是真正的用例，但我想为此编写一个测试来学习和玩耍。在生产环境中，对象的数量将限制在 20 个左右，但这些对象彼此连接的方式是无限的。

这以简化的方式说明了问题: thanks to source

以一个特定的人为起点，我想遍历整个图表并检查每条可能的路径一次而不会陷入无限循环。

假设 A 认识 B，谁认识 C，谁认识 A。输出可能是:

A 知道 B 知道 C 知道 A(好吧，但我们不想以无限循环结束，所以我们就此打住)A知道C知道AA知道T知道R知道V

这是愚蠢的，必须被消除:A知道B知道C知道A知道C知道A知道T知道R知道V ...

我确实有几个疯狂的想法来解决这个问题。但是……

问题)我必须使用迭代加深深度优先搜索 (IDDFS) 来做到这一点吗？

---

Jon 非常友善地指出 DFS on Wikipedia

我对文章中的这一部分感到困惑:

a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory.

特别是这个注释:

"(since this is a small graph)"

好吧，如果这是一个巨大的图表呢？

Answer 1

编辑:我应该提到作者的标题和问题已经改变了很多，这个答案中的一些信息可能不是 100% 相关。

正如 Jon 已经提到的，这确实是一个图表。实际上是有向图。

我建议你看看Adjacency matrices ，他们将为您提供有关如何找到解决方案的直接见解。我想您最初的惰性 解决方案可能类似于 Adjacency list。 ;这很好，但实现起来并不容易，而且可能更难遍历。两者之间有两个主要区别。

邻接表会占用更多空间，但在较大的网络中可能更好地减少对未连接节点的计算；而邻接矩阵稍微友好一些，但会为每条边存储数据，无论它是否存在(连接)。

我在使用邻接表时发现的主要问题不是它们的理论空间，而是在 C++ 中，我将每个连接的节点作为指针存储在每个节点内的向量中；一旦网络变大，这可能会失控，并且对于可视化以及管理新节点和删除节点非常不友好。与邻接矩阵相比，邻接矩阵对所有节点都有一个引用(可以存储在单个节点向量中)并且可以很容易地修改。

---

如果您的问题确实是关于遍历的，那么如果您的图是作为邻接矩阵实现的，作为向量的向量，遍历很简单。见下面的伪代码:

读取(对于每个神经元)神经元的轴突连接到的所有神经元(即神经元输出)

for (size_t i = 0; i < n; ++i) { // adjacency matrix is n * n
    Neuron& neuron = nodes[i];
    for (size_t j = 0; i < n; ++i) {
        Axon_connection& connection = edges[j][i];
        if (connection.exists()) {
            ...
        }
    }
}

读取神经元树突连接的所有(对于每个神经元)神经元(即神经元输入)

for (size_t i = 0; i < n; ++i) { // adjacency matrix is n * n
    Neuron& neuron = nodes[i];
    for (size_t j = 0; i < n; ++i) {
        Dendrite& dendrite = edges[j][i];
        if (dendrite.exists()) {
            ...
        }
    }
}

请注意，根据您的实现情况，第二种方法可能对大型网络缓存不友好。exists 方法只是确保邻接矩阵位设置为 true，然后您可以实现其他数据，例如这些边的强度。