斯卡拉：如何查找和有向圖

返回一個糊塗的路徑我寫了Scala中的一個功能，找出並有向圖中返回一個糊塗的路徑。該程序如下，其中一個參數是在相鄰列表中呈現的圖形，另一個是起始節點。它通過節點列表返回一個包含循環路徑的對。斯卡拉：如何查找和有向圖

不知有更優雅的方式來做到這一點。如果您願意，請分享您的想法。謝謝。我覺得我不得不在這種情況下使用indexWhere，但我想它會有其他方法來做到這一點。

2012-12-10 Qi Qi

我認爲http://codereview.stackexchange.com/是這類問題的好地方。 – 4e6

@ 4e6謝謝！ –

我只是張貼在相關的StackOverflow問題更通用的FP一成不變的答案：http://stackoverflow.com/a/36144158/501113 – chaotic3quilibrium

您應該使用數組來檢查，如果你已經訪問過的一個節點，而不是visits.contains(node)，它會給你一定的時間，而不是線性時間的答案。

算法的整體複雜性是指數級的。舉例來說，如果你運行你在這個圖算法：

0 -> 1, 2, ..., n 
1 -> 2, ..., n 
...

那裏有n節點，也有從邊緣到i當且僅當j然後i<j節點i將探討2^i倍。

同樣可以使用一個數組（一個陣列所有節點），以確保每個節點至多一個時間探索解決該問題。

2012-12-10 10:46:54 Thomash

謝謝，@Thomash。使用數組是一個很好的建議。但是，這種算法不會呈指數增長，因爲它首先在深度搜索中運行，並且每遇到一條循環路徑，就會立即返回並退出，但不會探索其他算法。 .indexWhere（p => Boolean）將在其謂詞爲真時停止。 –

如果你不相信我，當我說它是指數的時候，在我的例子中用n = 100來測試你的函數。 – Thomash

我認爲程序使用深度優先搜索（DFS）傳播圖形，不是嗎？ DFS的複雜性是O（n），引用http://en.wikipedia.org/wiki/Depth-first_search。 –

回答