功能廣度優先搜索

功能深度優先搜索在有向無環圖中是可愛的。功能廣度優先搜索

但是在循環圖中，我們如何避免無限遞歸？在程序語言中，我會在點擊節點時標記節點，但假設我不能那樣做。

已訪問節點的列表是可能的，但會很慢，因爲使用一個會在重複出現之前導致該列表的線性搜索。比這裏的列表更好的數據結構顯然會有所幫助，但這不是遊戲的目的，因爲我在ML中編碼 - 列表是國王，還有其他任何我必須自己寫的。

有沒有一個巧妙解決這個問題的方法？或者我會不得不做一個訪問列表或上帝保佑，可變狀態？

來源

2015-05-26 N. McA.

在Python可以創建訪問節點的'set'，使得查找'O（1）'，而不是'爲O（n）'。 – jonrsharpe

我敢打賭，*單子*可以處理它.. –

如何使用合適的數據結構*不*遊戲的目的是什麼？ – chepner

一種選擇是使用歸納圖，這是表示和使用任意圖結構的功能方式。它們由Haskell的fgl庫提供，並在Martin Erwig的"Inductive Graphs and Funtional Graph Algorithms"中描述。

對於一個溫和的介紹（帶插圖！），請參閱我的博客文章Generating Mazes with Inductive Graphs。

感應圖的訣竅是他們讓你模式匹配圖。用於處理列表的常見的功能性成語是將它們分解成一個頭元素和列表的其餘部分，然後遞歸上：

map f []  = [] 
map f (x:xs) = f x : map f xs

感應圖可以做同樣的事情，但對於圖形。您可以將一個歸納圖分解爲一個節點，其邊和圖的其餘部分。

pattern matching on a node http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/match1.png

在這裏，我們匹配節點1及其所有邊緣（以藍色突出顯示），從圖中的其餘部分分開上。

這讓我們寫圖一map（在可與模式同義詞實現Haskellish僞代碼）：

gmap f Empty      = Empty 
gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest

，而不是列出了該方法的主要缺點是圖形沒有單一的自然分解方式：可以用多種方式建立同一個圖。上面的地圖代碼將訪問所有的頂點，但是以任意（依賴於實現）的順序訪問。

爲了克服這個問題，我們添加另一種構建：一個match功能，需要一個特定的節點。如果該節點在我們的圖中，我們就會像上面那樣獲得成功的匹配;如果不是，整場比賽都會失敗。

此結構是足夠寫一DFS或BFS-與優雅的代碼，看起來兩個幾乎一模一樣！

除了手動將節點標記爲已訪問，我們只是在圖的其餘部分遞歸，除了我們現在看到的節點：在每一步，我們正在處理原始圖的越來越小的部分。如果我們嘗試訪問我們已經看到的節點match，它將不在剩餘的圖中，並且該分支將失敗。這讓我們的圖形處理代碼看起來就像我們在列表上的正常遞歸函數。

這裏有一個DFS的這種圖形。它保持節點堆棧訪問作爲列表（邊界），並採用最初的邊界開始。輸出是按順序遍歷的節點列表。（這裏的確切的代碼不能與庫中直接寫入沒有一些自定義模式的同義詞。）

dfs _frontier Empty = [] 
dfs [] _graph = [] 
dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n 
    dfs (neighbors' ctx ++ ns) rest 
dfs (n:ns) graph =       -- visited n 
    dfs ns graph

一個非常簡單的遞歸函數。爲了把它變成一個廣度優先搜索，我們所要做的就是與隊列代替我們棧前沿：而不是把鄰居的列表中的前，我們把它們放在回：

bfs _frontier Empty = [] 
bfs [] _graph = [] 
bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n 
    bfs (ns ++ neighbors' ctx) rest 
bfs (n:ns) graph =       -- visited n 
    bfs ns graph

是的，這就是我們所需要的！就像我們不必跟蹤我們訪問過的列表單元格一樣，我們不需要做任何特別的事情來跟蹤我們訪問的節點，就像我們不必跟蹤我們訪問過的列表單元格一樣：每次我們遞歸時，重新只得到圖中我們沒有看到的部分。

來源

2015-05-26 21:29:45

這很美。謝謝。 –