Python递归实现：查找最终父节点路径并计算所有权占比

给定包含三列的数据集：子实体、父实体、父实体对子实体的所有权百分比，数据如下：

Child   Parent   Ownership
   A       B         50%
   C       D         10%
   B       C         20%
   E       D         30%
   B       E         40%

其中D为最终父节点，需计算D在每个子实体中的所有权百分比。计算规则：找到所有从子实体指向D的路径，将每条路径上的所有权百分比相乘，多条路径结果相加。预期结果：

For A: [A->B->C->D],[A->B->E->D]. D_ownership = 50%*20%*10% + 50%*40%*30%=7%
For B: [B->C->D],[B->E->D]. D_ownership = 20%*10% + 40%*30% = 14%
For C: [C->D]. D_ownership = 10%
For E: [E->D]. D_ownership = 30%

最初用嵌套循环实现过于复杂，希望通过图搜索（DFS/BFS）或递归方式解决，但不确定如何将数据集转换为图结构及节点处理方式。

1. 转换数据集为图结构 #

把原始数据转换成子实体到父实体的映射字典，键为子实体，值是列表，每个元素存储(父实体, 所有权小数)（先去掉百分号转成小数，方便后续计算）。示例结构：

graph = {
    'A': [('B', 0.5)],
    'B': [('C', 0.2), ('E', 0.4)],
    'C': [('D', 0.1)],
    'E': [('D', 0.3)]
}

这样可以快速查询任意节点的所有父节点及对应所有权比例。

2. 带记忆化的递归/深度优先搜索（DFS）计算所有权 #

核心逻辑是递归遍历每个节点到D的所有路径，累加每条路径的乘积：

• 终止条件：若当前节点是D，返回1.0（到达最终节点，路径乘积的基础值）；若当前节点无父节点且不是D，返回0.0（无有效路径）。
• 递归逻辑：遍历当前节点的所有父节点，计算父节点到D的所有权，再乘以当前节点到父节点的比例，将所有结果累加。
• 记忆化优化：用字典缓存已计算过的节点结果，避免重复递归计算（比如A和B都需要计算C到D的所有权，缓存后只需计算一次）。

3. 代码实现示例 #

def calculate_ownership(node, graph, target='D', memo=None):
    # 初始化记忆缓存
    if memo is None:
        memo = {}
    # 终止条件：到达目标节点
    if node == target:
        return 1.0
    # 已计算过的节点直接返回缓存结果
    if node in memo:
        return memo[node]
    
    total = 0.0
    # 节点无父节点，返回0
    if node not in graph:
        memo[node] = total
        return total
    
    # 遍历所有父节点，递归计算并累加结果
    for parent, ratio in graph[node]:
        total += ratio * calculate_ownership(parent, graph, target, memo)
    
    # 缓存当前节点结果
    memo[node] = total
    return total

# 构建图结构
graph = {
    'A': [('B', 0.5)],
    'B': [('C', 0.2), ('E', 0.4)],
    'C': [('D', 0.1)],
    'E': [('D', 0.3)]
}

# 计算并输出每个节点的所有权
nodes = ['A', 'B', 'C', 'E']
for node in nodes:
    ownership = calculate_ownership(node, graph)
    print(f"For {node}: D_ownership = {ownership * 100:.1f}%")

运行结果：

For A: D_ownership = 7.0%
For B: D_ownership = 14.0%
For C: D_ownership = 10.0%
For E: D_ownership = 30.0%

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