递归函数使用的全局变量

假设您必须使用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数组：

，我们可以把它定义为一个私有字段为每个DFS像visitedConnectivity，visitedTopSorting，visitedBridges等，所以我们有很多的Graph的每个实例私有变量。如果我们每个dfs有3-4个这样的“全局”变量呢？
我们可以通过visited作为dfs的论点。在这种情况下，我们将在每次dfs调用时都有开销。

那么，这个问题最简单和真实世界使用的解决方案是什么？当然，它不仅与图算法有关，但我发现用dfs术语解释它更容易。

来源

2011-12-25 karlicoss

更OOP的方式，在我看来，是delcaring场visited每个DFS类，并使其运行自己的DFS ....

它会阻止你跟踪“我分配做了什么？它在哪里连接？等等......”

你DFS将更加封装，并需要更少的数据，然后将每个DFS，你将不得不单独维护一个额外的参数。

在这里的性能问题忽略[在大多数情况下]的可读性和maintainability你实现尽可能多的封装在类本身

来源

2011-12-25 21:20:45 amit

作为参数传递visited。没有开销！

更新OK我纠正了。让我说可以忽略的开销;）但是，我会选择在堆栈中保留一个指针，使其具有一个在函数之外没有意义的字段/全局变量，并在每天完成后进行记忆。

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

来源

2011-12-25 21:13:50 Nicolas78

为什么你说没有开销？如果visited是一个'vector'，它将被复制 - 如果它是一个数组，这不会解决问题，因为它只能通过引用传递。你能解释一下你的逻辑吗？ – amit 2011-12-25 21:16:27

我正在考虑通过引用NCE。为什么这不能解决问题？ – Nicolas78 2011-12-25 21:18:21

有。在每次调用时，一个指向'visited'的指针将被存储在调用堆栈中。 – karlicoss 2011-12-25 21:18:24

你可以使用静态变量！

来源

2011-12-25 21:17:46 PeterP

他们将如何帮助？你能详细说明吗？ – amit 2011-12-25 21:31:15

递归函数使用的全局变量

回答

相关问题