Python 递归找上游

Question

#背景
cur_table source_table
A C
A B
B D
D E
… …
现在有一张表，里面存着两个字段，cur_table代表现有的表，source_table代表现在的表对应的上游表；如图，表A对应的上游表有C和B，B对应的上游表为D，D对应的上游表为E；

#问题
通过Ptyhon 或者 SQL，实现找到现有表的所有上游相关表；
如
A：C,B,D,E
B：D,E
D：E

背景列的只是举例，实际表中，现有表相关的血缘关系可能有上百层；本人目前会使用SQL，重复left join的笨办法，不能解决血缘关系数量多的情景；

Answer 1

• 下列程序从标准输入读取字符串，直到遇到空行为止。每行的格式为 "当前表 上游表"，用一个空格隔开。例如，"table1 table2" 表示 "table1" 表依赖于 "table2" 表。

• 接下来，程序遍历字典的每个键，并计算出那些表是这个表的下游表（即依赖于这个表的表）。为了计算下游表，程序从当前表开始，递归地搜索上游表，直到所有的上游表都被搜索完为止。最后，将计算出的下游表集合更新到字典中。

• 最后，程序打印出构建的字典。结果应该是每个表及其所有下游表的列表。

# 建立空字典，用于存储每个表格的来源
upstream_tables = {}

# 逐行读入字符串
for index, row in df.iterrows():
    # 拆分为两个单词
    cur_table, source_table = row[0], row[1]
    # 为当前表格建立来源集合，或将来源表格加入来源集合
    upstream_tables.setdefault(cur_table, set()).add(source_table)

# 遍历所有表格
for key in upstream_tables.keys():
    # 取出当前表格的来源表格集合
    downstream_table = upstream_tables[key]
    # 建立临时集合，用于存储间接来源表格
    temp = set()
    # 当来源表格集合不为空时
    while downstream_table:
        # 取出来源表格集合中的一个表格
        a = downstream_table.pop()
        # 将其加入临时集合
        temp.add(a)
        # 如果这个表格还有来源表格
        if a in upstream_tables:
            # 将这些来源表格加入来源表格集合
            downstream_table.update(upstream_tables[a])
    # 将临时集合存回字典
    upstream_tables[key] = temp

# 输出上游表
print(upstream_tables)
# 输出结果df
res_df = pd.DataFrame({'cur_table': upstream_tables.keys(), 'source_table': upstream_tables.values()})