遞歸函數使用的全局變量

假設您必須使用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

遞歸函數使用的全局變量

回答

相關問題