给定词典列表：
[{"a": ["b", "c", "d"]},
{"b":["e", "z", "g"]},
{"g":["c", "f", "z"]},
{"z":["w", "y", "x"]}]
暗示
"a""b", "c", and "d""a""e", "z", "g", "f", "w", "y", "z"因此我正在寻找一个深度搜索，它可以给出每个键的字典列表及其各自的间接依赖项（不包括直接依赖项），这样上面数据的结果输出看起来像：
[{"a": ["e", "z", "g", "f", "w", "y", "z"]},
{"b":["c", "f",, "w", "y", "x"]},
{"g":["w", "y", "x"]},
{z:[]}]
这里是您问题的可能解决方案：
def dfs(dictionary : dict, start : str, visited : set) -> set:
# Add the current key to the visited set
visited.add(start)
# If the current key has no dependencies return the visited set
if dictionary.get(start) is None:
return visited
# For each dependency of the current key, if it is not visited, call dfs on it
# This will find all the dependencies of that dependency and so on, until there are no more dependencies.
for value in dictionary.get(start):
if value not in visited:
dfs(dictionary, value, visited)
# Return the visited set
return visited
def indirect_dependenices(list_of_dictionaries : list) -> list:
# Merge all the dictionaries into one
merged_dictionary = {key:value for dictionary in list_of_dictionaries for key,value in dictionary.items()}
# Initialize the output list
output = []
for key in merged_dictionary:
visited = set()
# for each key in the dictionary find among the other all its dependencies (both direct and indirect)
dependencies = dfs(merged_dictionary, key, visited)
# remove the direct dependencies
dependencies = dependencies - set(merged_dictionary.get(key)) - set(key)
# add the key and its indirect dependencies to the output
output.append({key: list(dependencies)})
return output
def main():
# Initialize the list of dictionaries
list_of_dictionaries = [{"a": ["b", "c", "d"]}, {"b":["e", "z", "g"]}, {"g":["c", "f", "z"]}, {"z":["w", "y", "x"]}]
output = indirect_dependenices(list_of_dictionaries)
print(output)
if __name__ == "__main__":
main()
提供的代码首先将字典列表合并到一个字典中，然后循环遍历所有键并执行 DFS 以查找该键的所有依赖项（直接和间接）。在将结果附加到输出之前，直接依赖项从列表中删除。
您可以使用递归函数来检查每个列表值是否是列表的键。
您需要使用一个函数来循环遍历每个键的值列表。如果找到的键是列表中的一个节点，则收集所有间接依赖项。该函数返回由“collect_dependencies”函数格式化的值列表。
递归函数“collect_dependencies”检查列表的每个值是否是列表的间接键。
def collect_dependencies(graph, node, dependencies):
"""
Recursive function to collect indirect dependencies for a given node in a graph
"""
if node not in graph: # If node is not in graph, return False
return False
for neighbor in graph[node]: # Looping through each neighbor of the node
if neighbor in graph: # Checking if the neighbor is a node in the graph
collect_dependencies(graph, neighbor, dependencies) # Collecting indirect dependencies for the neighbor
elif neighbor not in dependencies: # Checking if the neighbor is not already in the list of dependencies
dependencies.append(neighbor) # Adding the neighbor to the list of dependencies
def get_indirect_dependencies(graph):
indirect_dependencies = [] # List to store indirect dependencies
for key in graph.keys(): # Looping through each node in the graph
dependencies = [] # List to store dependencies for each node
for neighbor in graph[key]: # Looping through each neighbor of the node
if neighbor in graph: # Checking if the neighbor is a node in the graph
collect_dependencies(graph, neighbor, dependencies) # Collecting indirect dependencies for the neighbor
if not dependencies: # Checking if there are any dependencies
continue # If there are no dependencies, skip to the next node
indirect_dependencies.append({key: dependencies}) # Adding the node and its dependencies to the list of indirect dependencies
return indirect_dependencies
graph = {
"a": ["b", "c", "d"],
"b": ["e", "z", "g"],
"g": ["c", "f", "z"],
"z": ["w", "y", "x"],
}
indirect_dependencies = get_indirect_dependencies(graph)
for dependency in indirect_dependencies:
print(dependency)