Haskell深度优先图遍历出现无限循环问题求助

你的DFS遍历代码陷入无限循环的核心原因是回溯逻辑错误：原代码通过字符大小比较选择回溯节点，完全偏离了DFS回溯到父节点的正确逻辑，导致在某些分支中反复访问同一节点，无法回到起点处理未探索的分支（比如第二个用例中的E节点）。

错误回溯逻辑的影响 #

以第二个用例为例，当遍历到B节点后无未访问邻接节点时，原代码会错误地回溯到D节点，之后又从D回溯到B，陷入B→D→B的无限循环，永远无法回到A节点去访问E。

修正后的Haskell代码 #

import Data.List (elem)

trav :: [(Char, String)] -> Char -> Char -> String -> String
trav [] _ _ _ = []
trav graph node endNode visited
    | not (elem node visited) = trav graph node endNode (visited ++ [node])
    | node == endNode = visited
    | not (null unvisitedNodes) = trav graph (head unvisitedNodes) endNode visited
    | length visited >= 2 = let parent = visited !! (length visited - 2)
                            in trav graph parent endNode (visited ++ [parent])
    | otherwise = visited
    where
        unvisitedNodes = [x | x <- getAttachedVertexes graph node, not (elem x visited)]

getAttachedVertexes :: [(Char, String)] -> Char -> [Char]
getAttachedVertexes graph node = case lookup node graph of
    Just value -> value
    Nothing -> ""

修正后的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) >= 2:
        parent = visited[-2]
        return trav(graph, parent, endNode, visited + [parent])
    return visited

def getAttachedNodes(graph, node):
    return graph.get(node, [])

if __name__ == '__main__':
    graph1 = {"A":["B", "C"], "B":["A", "C", "D"], "C":["A", "B"], "D":["B"]}
    graph2 = {"A":['C', 'D', 'E'], "B":['D'], "C":['A','D'], "D":['A','B','C'], "E":['A']}
    node = input("Node: ")
    endNode = input("EndNode: ")
    print(trav(graph2, node, endNode, []))

关键修改说明 #

1. 移除错误的回溯逻辑：删掉了基于字符大小选择回溯节点的prevIndex相关代码。
2. 正确回溯到父节点：当当前节点无未访问邻接节点时，直接回到当前路径的父节点（路径的倒数第二个元素），并将父节点加入路径，继续递归处理父节点的其他未探索分支。
3. 保留原需求的路径记录：依然按照你的要求记录所有访问步骤（包括回溯时的节点重复添加），比如第一个用例仍会输出ABCBD。

内容的提问来源于stack exchange，提问作者lrainey6-eng