简单有向无环图中的哈密顿路径

以下是一个用Python实现的简单有向无环图中的哈密顿路径的解决方法：

def is_hamiltonian_path(graph):
    def dfs(node, path):
        if len(path) == len(graph):
            return True  # 找到了哈密顿路径
        for neighbor in graph[node]:
            if neighbor not in path:
                path.append(neighbor)
                if dfs(neighbor, path):
                    return True
                path.remove(neighbor)
        return False

    for start_node in graph.keys():
        path = [start_node]
        if dfs(start_node, path):
            return True
    return False

# 示例用法
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': []
}
print(is_hamiltonian_path(graph))  # 输出 True

上述代码使用了深度优先搜索（DFS）算法来查找哈密顿路径。首先定义了一个内部的dfs函数，它接受当前节点和已经访问过的路径作为参数。如果路径的长度等于图的节点数量，说明找到了哈密顿路径，返回True。否则，遍历当前节点的邻居节点，如果邻居节点没有在路径中出现过，则将它添加到路径中，并递归调用dfs函数。如果递归调用返回True，说明找到了哈密顿路径，返回True。否则，将邻居节点从路径中移除，继续遍历其他邻居节点。如果所有的邻居节点都遍历完了仍然没有找到哈密顿路径，则返回False。

在示例用法中，定义了一个简单的有向无环图，然后调用is_hamiltonian_path函数来判断是否存在哈密顿路径。根据给定的图，输出结果为True，表示存在哈密顿路径。