递归函数使用的全局变量

Question

假设您必须使用dfs (深度优先搜索)实现包含一些算法的Graph类。例如，可能是连接检查，Graph类如下所示：

class Graph {
    void dfsConnected(int v) {
        visited[v] = true;
        //indexing over v's adjacencies and calling dfsConnected recursively
    }
    bool isConnected {
        //indexing over vertice list and calling dfsConnected
    }
}

假设我们有很多算法，在这个类中使用dfs (每个算法都使用特定的dfs)。问题是visited数组：

• 我们可以将它定义为visitedConnectivity、visitedTopSorting、visitedBridges等每个dfs的私有字段，因此在Graph的每个实例中都会有很多私有变量。如果每个dfs都有3-4个这样的“全局”变量呢？
• 我们可以将visited作为dfs的参数传递，在这种情况下，每个dfs调用都会有开销。

那么，对于这个问题，最简单、最真实的解决方案是什么呢？当然，它不仅与图形算法有关，而且我发现用dfs术语解释它更容易。

Answer 1

在我看来，更多的OOP方式是为每个DFS类删除一个字段visited，并使其运行自己的DFS.

它将阻止你跟踪‘我分配了什么?它连接到哪里?等等……’“

您的dfs将被封装得更多，需要更少的数据，然后为每个DFS添加一个额外的参数，您必须单独维护这些参数。

这里的性能问题在大多数情况下忽略了可读性和通过在类本身中封装尽可能多的数据而实现的维修性。

Answer 2

传递visited作为一个参数。没有头顶！

更新，好，我被纠正了。尽管如此，我还是会选择在堆栈中保留一个指针，而不是在函数之外有一个没有意义的字段/全局变量，并在它每天完成之后吃掉内存。

如果您真的关心的话，您可以将DFS封装在一个具有自己的visited字段并将图形作为参数的对象中。但即便如此，这也可能转化为堆栈上带有对象指针的函数调用。

Answer 3

你可以使用静态变量！