Scala：遞歸搜索避免週期

如何編寫一個遞歸搜索來避免週期。Scala：遞歸搜索避免週期

我的班級是這樣的：

class Component(var name: String, var number: Int, var subComponent: Set[Component])

現在我需要一種方法來檢查組件是否包含其子內或在其子的子等引起的組件，以便on.Avoiding可能週期之間。

我的遞歸搜索方法必須有以下簽名，其中subC是組件的[組件]。

def content (comp: Component, subC: Set[Component]) : Boolean = { 
}

感謝您的幫助。

來源

2012-12-08 user1826663

這聽起來像一個家庭作業問題，如果你的簽名_必須是。在這種情況下，這裏有一個方便的提示。編寫一個遞歸搜索的算法。然後，只有在你點擊一個新元素後纔會遞歸。你怎麼知道它是新的？爲什麼，如果它不在你的設置中 - 只要你看到一些東西，就把它添加進去！（獎勵要點：保留整個歷史記錄，而不僅僅是沿着當前遞歸路徑的歷史記錄，所以避免多次遍歷同一元素以及循環。） –

一種方法是用累加器定義一個內部函數。

def content (comp: Component, subC: Set[Component]) : Boolean = { 
    def contained(comp: Component, subC: Set[Component], visited: Set[Component]): Boolean = { 
     // over time (recursion) add components to visited 
     // you can then use 
     // visited contains comp 
     // to check existence and 
     // visited diff subC 
     // to get the unvisited components 

    } 
}

來源

2012-12-08 10:58:25

最簡單的實現方法是保留一組訪問過的組件。這可以被定義爲你的方法中的一個方法。該方法將執行遞歸。它將把訪問集作爲一個額外的參數，並將用一個空集來啓動。

來源

2012-12-08 11:02:00 thoredge

Scala：遞歸搜索避免週期

回答

相關問題