我最近花了一些时间在Haskell中尝试做一个深度优先遍历算法，但是，我希望这个函数返回一个“访问过的”列表，其中按顺序列出了每个访问过的节点。
演示：对于图形[('A', "BC"), ('B', "ACD"), ('C', "AB"), ('D', "B")]，输出应该是"ABCBD"，因为我从A开始，到D结束。
下面是我的代码：
import Data.List (elemIndex)
trav :: [(Char, String)] -> Char -> Char -> String -> String
trav [] _ _ _ = []
trav graph node endNode visited
| not (elem node visited) = trav graph node endNode (visited ++ [node]) -- repeat but after adding this node to visited list.
| node == endNode = visited
| not (null unvisitedNodes) = trav graph (head unvisitedNodes) endNode visited
| not (null visited) = if (length prevIndex) > 1 then (trav graph (visited !! (getIndex (head prevIndex) visited)) endNode (visited ++ [(visited !! (getIndex (head prevIndex) visited))])) else (trav graph (head (tail (reverse visited))) endNode (visited ++ [(head (tail (reverse visited)))]))
| otherwise = visited
where
unvisitedNodes = [x | x <- getAttachedVertexes graph node, not (elem x visited)]
prevIndex = [x | x <- (reverse visited), x < (head (reverse visited))]
getAttachedVertexes :: [(Char, String)] -> Char -> [Char]
getAttachedVertexes graph node = case lookup node graph of
Just value -> value
Nothing -> ""
getIndex :: Eq a => a -> [a] -> Int
getIndex item list = case elemIndex item list of
Just index -> index
Nothing -> error "help"字符串
这段代码实际上运行良好，输出了我在上面写的理想输出，输入如下：trav [('A', "BC"), ('B', "ACD"), ('C', "AB"), ('D', "B")] 'A' 'D' ""
但是，当我输入以下输入时，此代码将启动无限递归循环：trav [('A', "CDE"), ('B', "D"), ('C', "AD"), ('D', "ABC"), ('E', "A")] 'A' 'E' ""
显然没有错误消息，因为它是一个无限循环。
我的思考过程：
我刚刚用更新的Haskell代码编辑了这个问题，这是以下思考的结果：
我最初认为问题的一部分是，在回溯时，回溯到的节点被添加到了visited列表中，这意味着当我执行head (tail (reverse visited))时，返回的项实际上是当前正在遍历的同一个节点。
我把这段代码“翻译”成Python 3，这是我最有经验的语言，并把它保存为Haskell格式，也就是一个包含一系列if语句的函数，所有语句中都有一行return。
接下来，我尝试修复上面的错误。它返回了我上面提到的第一个输入的正确输出（{"A":["B", "C"], "B":["A", "C", "D"], "C":["A", "B"], "D":["B"]}），但是，当我尝试上面的第二个输入（{"A":['C', 'D', 'E'], "B":['D'], "C":['A','D'], "D":['A','B','C'], "E":['A']}）时，它再次开始了一个无限循环（嗯，至少直到堆栈溢出）。
下面是Python代码：
def trav(graph, node, endNode, visited):
if node not in visited:
return trav(graph, node, endNode, (visited + [node]))
if node == endNode:
return visited
unvisitedNodes = [x for x in getAttachedNodes(graph, node) if x not in visited]
if len(unvisitedNodes) > 0:
return trav(graph, unvisitedNodes[0], endNode, visited)
if len(visited) > 0:
prevIndex = [x for x in reversed(visited) if x < visited[-1]]
if len(prevIndex) > 1:
return trav(graph, visited[visited.index(prevIndex[0])], endNode, (visited + [visited[visited.index(prevIndex[0])]]))
else:
return trav(graph, visited[-2], endNode, (visited + [visited[-2]]))
return visited
if __name__ == '__main__':
graph1 = {"A":["B", "C"], "B":["A", "C", "D"], "C":["A", "B"], "D":["B"]}
node = input("Node: ")
endNode = input("EndNode: ")
graph2 = {"A":['C', 'D', 'E'], "B":['D'], "C":['A','D'], "D":['A','B','C'], "E":['A']}
visited = []
print(trav(graph2, node, endNode, visited))型
我重新编写了Haskell代码，现在它在所有测试用例中的运行方式与上面的Python代码完全相同。显然，这只对那些精通Python的人有帮助。我编写它是为了希望能够理解这个问题。我的下一个编辑将是调试这个Python代码的结果。
我为它的混乱和低效率道歉，但我想尽可能地反映上述Haskell代码。
不管怎样，我把它包括进来，希望能让我的算法更清晰。
总之，问题不是我所解释的，我以为只是上面的问题。
再次感谢
3条答案
按热度按时间eyh26e7m1#
我刚刚解决了这个问题。下面是更新后的Haskell代码：
字符串
下面是更新后的等价Python代码：
型
我意识到，无限循环是由于，每当需要回溯时，程序只返回一个节点，但随后将该节点添加到访问列表中，因此
head (tail (reverse visited))（或Python等效的visited[-2]）意味着程序在两个节点之间不断前进。正如你在新的Python翻译中可以清楚地看到的那样，我现在去visited[-2]* 除非 * 有一个连接的节点与未访问的相邻节点。现在，它可以处理我测试过的所有图形。
非常感谢大家的帮助！
ktca8awb2#
@lrainey6-eng，
首先，正如@willeM_货车Onsem在对你的问题的评论中指出的那样，你的树中有循环。让我们用不同的输入来尝试一下。让我们对一个节点列表尝试一下：[（'A'，“BC”），（'B'，“DE”），（'C'，“FG”），（'D'，“HI”），（'E'，“JK”），（'F'，“LM”），（'G'，“NO”）].如果我们从'A'开始搜索'O'，我们应该期待“ABDHIEJKCFLMGN”的路径.正确吗？
字符串
我不能遵循你的程序，但我写了我自己的比较。我想尝试把它放到Python中，只是为了体验。无论如何，这是我想到的：
型
如果我们运行：
pathTo [('t',"Hr"),('h',"ij"),('q',"sT"),('i'," tE"),('T',"r"), (' ',""),('E',"!q"),('H',"e")] 'q'，会得到什么？nbewdwxp3#
的数据
在我之前的回答中（见上文），我包含了一个深度优先搜索树的程序，其中节点不会循环回自己。有人向我指出，这里的问题涉及到可以循环回的图。在这里，我将修改之前的程序，使其也适用于一般的图（包括树）。
将上面的树程序修改为图通常需要一些修改。如果没有明确的根节点，函数
pathTo就返回Nothing，就像树一样。相反，一般的图使用一个名为pathFromTo的函数，它接受一个起始点和一个目标标签。（下面的代码中没有包含，请参阅前面的答案）最大的区别出现在
expand函数中，这是程序的核心。以前，对于树，我们可以将相同的节点列表传递给每个递归扩展而不用担心，因为永远不会有扩展导致自身的另一次扩展和无限循环的情况。对于图，深度搜索路径要求，当每个节点被展开时，将其从节点列表中移除，因此它不能被再次展开或“访问”。另外一个函数
remove删除了带有给定标签的节点和子节点。此外，我们之前允许节点列表包含没有显式列出为终端节点（“leaves”）的子节点。这导致了不必要的复杂性，因此我们必须坚持（通过不变量的方式）子节点作为节点包括在内，如下所示：[('A',"BC"),('B',""),('C',"") … ]。字符串
因为搜索路径在最左边的分支之前展开，所以子节点的展开依赖于从它们左边的分支返回的节点列表。这意味着我们不能再像以前那样使用
concatMap（expand nodes）（getSubs label nodes）对所有子节点平等地使用简单Map。现在我们需要使用一个递归函数，将修改后的节点列表传递给每个后续的子节点展开。有了这些变化，只针对树的基本程序将适用于一般的图。
比较：
型
收件人：
型
注意事项：在
otherwise = label : leftPath ++ recOnRSubs …这一行，我已经把最左边的子节点展开为显式的，然后再转到右边的子节点上的递归。这不是严格必要的。可以使用子节点上的递归版本来包括最左边的节点，但我喜欢左边路径的显式。我认为这有助于读者定位。