如何用Perl实现DFS查找De Bruijn图的所有欧拉路径并筛选最长路径

现有代码的核心问题 #

• 找到第一个未访问的边就直接break，只探索了单条分支，没有遍历所有可能的子节点
• 边的标记是永久修改原哈希，递归返回后没有恢复状态，导致其他分支无法访问这条边
• 没有收集所有路径的逻辑，只维护了单个路径数组

修正方案：回溯式DFS #

要遍历所有欧拉路径，必须用回溯法：每次递归探索一条边后，完成该分支的遍历要恢复边的可用状态，同时收集所有合法的完整路径。另外，你的哈希中边的第一个值是出现频率，所以不能只用0/1标记，应该基于剩余可用次数来判断是否能走这条边。

修正后的代码实现 #

# 用于保存所有找到的欧拉路径
my @all_paths;

sub dfs_euler {
    my ($graph, $current_node, $current_path, $total_edges) = @_;

    # 把当前节点加入路径
    push @$current_path, $current_node;

    # 终止条件：路径节点数等于总边数+1（欧拉路径的节点数=边数+1）
    if (@$current_path == $total_edges + 1) {
        # 保存路径副本，避免后续修改影响已保存的结果
        push @all_paths, [@$current_path];
        # 回溯：移除当前节点，返回上一层
        pop @$current_path;
        return;
    }

    # 遍历当前节点的所有邻接边
    foreach my $next_node (keys %{$graph->{$current_node}}) {
        # 取当前边的剩余可用次数
        my $remaining = $graph->{$current_node}{$next_node}[0];
        if ($remaining > 0) {
            # 消耗一次可用次数
            $graph->{$current_node}{$next_node}[0]--;
            # 递归探索下一个节点
            dfs_euler($graph, $next_node, $current_path, $total_edges);
            # 回溯：恢复可用次数
            $graph->{$current_node}{$next_node}[0]++;
        }
    }

    # 回溯：移除当前节点，返回上一层
    pop @$current_path;
}

# 计算图中总边数（所有边的出现频率之和）
sub calculate_total_edges {
    my ($graph) = @_;
    my $total = 0;
    foreach my $node (keys %$graph) {
        foreach my $child (keys %{$graph->{$node}}) {
            $total += $graph->{$node}{$child}[0];
        }
    }
    return $total;
}

# 使用示例
my $debruijn_graph = {
    'ATTCA' => {
        'TTCAA' => [4, 0],
        'TTCAT' => [1, 0]
    },
    'TTCGT' => {
        'TCGTT' => [1, 0],
        'TCGTA' => [1, 0]
    },
    'AGAAG' => {
        'GAAGT' => [1, 0]
    },
    # 需补充完整节点的邻接关系，否则路径会提前终止
};

my $total_edges = calculate_total_edges($debruijn_graph);
# 可根据欧拉路径规则筛选起始节点（比如出度比入度大1的节点），减少无效遍历
my @start_nodes = keys %$debruijn_graph;

foreach my $start_node (@start_nodes) {
    my @current_path;
    dfs_euler($debruijn_graph, $start_node, \@current_path, $total_edges);
}

# 筛选最长路径（若存在欧拉路径，最长路径即为总边数+1长度）
my @sorted_paths = sort { scalar(@$b) <=> scalar(@$a) } @all_paths;
my $longest_path = $sorted_paths[0];

# 输出结果
print "最长欧拉路径：", join(" -> ", @$longest_path), "\n";

关键说明 #

1. 回溯机制：递归返回后恢复边的可用次数，确保其他分支可以重新访问这条边
2. 路径保存：每次完成完整路径时，保存路径的副本，避免后续修改影响已保存的结果
3. 终止条件：欧拉路径的节点数=总边数+1，以此判断是否遍历完所有边
4. 起始节点优化：根据欧拉路径存在规则，选择出度比入度大1的节点作为起始（欧拉路径），或任意节点（欧拉回路），可大幅减少无效遍历

De Bruijn图欧拉路径存在条件补充 #

• 欧拉路径：恰好一个节点出度比入度大1（起始），恰好一个节点入度比出度大1（终止），其余节点入度=出度
• 欧拉回路：所有节点入度=出度，任意节点可作为起始

提前验证这些条件可以避免无意义的遍历。

内容的提问来源于stack exchange，提问作者Laubiotec