首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在python中从字典中的一对(父,子)恢复路径?

在Python中,可以使用深度优先搜索(DFS)算法从字典中的一对(父,子)恢复路径。以下是一个完善且全面的答案:

深度优先搜索是一种用于遍历或搜索树或图的算法。在这个问题中,我们可以将字典看作是一个树结构,其中父节点是键,子节点是值。我们的目标是从给定的一对(父,子)中恢复路径。

以下是一个实现该算法的示例代码:

代码语言:txt
复制
def restore_path(dictionary, parent, child):
    # 创建一个空列表来存储路径
    path = []
    
    # 定义一个辅助函数来执行深度优先搜索
    def dfs(node, current_path):
        # 将当前节点添加到路径中
        current_path.append(node)
        
        # 如果当前节点是目标子节点,则将路径保存到全局变量中
        if node == child:
            path.extend(current_path)
        
        # 如果当前节点是父节点,则继续深度优先搜索其子节点
        if node in dictionary:
            for next_node in dictionary[node]:
                dfs(next_node, current_path)
        
        # 回溯,将当前节点从路径中移除
        current_path.pop()
    
    # 开始深度优先搜索
    dfs(parent, [])
    
    # 返回恢复的路径
    return path

使用示例:

代码语言:txt
复制
# 定义一个字典表示父子关系
dictionary = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H'],
    'E': ['I', 'J'],
    'F': ['K'],
    'G': ['L'],
    'H': [],
    'I': [],
    'J': [],
    'K': [],
    'L': []
}

# 恢复路径
parent = 'A'
child = 'J'
path = restore_path(dictionary, parent, child)
print(path)

输出结果为:['A', 'B', 'E', 'J']

在这个例子中,我们定义了一个字典表示父子关系。然后,我们调用restore_path函数,传入父节点为'A',子节点为'J'。函数将返回从父节点到子节点的路径['A', 'B', 'E', 'J']。

这个算法的时间复杂度是O(N),其中N是字典中节点的数量。在每个节点上,我们最多访问其所有子节点一次。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

何在字典存储值路径

Python,你可以使用嵌套字典(或其他可嵌套数据结构,嵌套列表)来存储值路径。例如,如果你想要存储像这样路径和值:1、问题背景在 Python ,我们可以轻松地使用字典来存储数据。...字典是一种无序键值对集合,键可以是任意字符串,值可以是任意类型数据。我们还可以使用字典来存储其他字典,这样就形成了一个嵌套字典。有时候,我们需要存储一个字典中值路径。...但是,如果我们需要存储 city 值路径呢?我们不能直接使用一个变量 city_field 来存储这个路径,因为 city 值是一个嵌套字典值。...2、解决方案有几种方法可以存储字典中值路径。第一种方法是使用循环。我们可以使用一个循环来遍历路径每个键,然后使用这些键来获取值。...第三种方法是使用自定义字典类。我们可以创建一个自己字典类,并在其中定义一个新方法来获取值路径

8610

零学习python 】21.Python元组与字典

元组 Python元组与列表类似,不同之处在于元组元素不能修改。元组使用小括号,列表使用方括号。...aTuple = ('et',77,99.9) aTuple 一、访问元组 二、修改元组 说明: python不允许修改元组数据,包括不能删除其中元素。...答: 字典 二、字典使用 定义字典格式:{键1:值1, 键2:值2, 键3:值3, …, 键n:值n} 变量info为字典类型: info = {'name':'班长', 'id':100,...'sex':'f', 'address':'地球亚洲中国上海'} info['name'] 说明: 字典和列表一样,也能够存储多个数据 列表找某个元素时,是根据下标进行字典找某个元素时,是根据’...名字’(就是冒号:前面的那个值,例如上面代码’name’、‘id’、‘sex’) 字典每个元素由2部分组成,键:值。

12610
  • 零学习python 】22. Python字典增删改查及字典变量

    二、修改元素 字典每个元素数据是可以修改,只要通过key找到,即可修改 info = {'name':'班长', 'id':100} print('修改之前字典为 %s:' % info)...info['id'] = 200 # 为已存在键赋值就是修改 print('修改之后字典为 %s:' % info) 结果: 修改之前字典为 {'name': '班长', 'id':...100} 修改之后字典为 {'name': '班长', 'id': 200} 三、添加元素 如果在使用 变量名[‘键’] = 数据 时,这个“键”在字典,不存在,那么就会新增这个元素 info =...info) 结果: 添加之前字典为:{'name': '班长'} 添加之后字典为:{'name': '班长', 'id': 100} 四、删除元素 对字典进行删除操作,有以下几种: del...遍历字典key(键) 遍历字典value(值) 遍历字典项(元素) 遍历字典key-value(键值对) 练习 有一个列表persons,保存数据都是字典 persons =

    12610

    python subprocess运行进程实时获取输出

    起因是这样,c++程序开发后 功能号和指令,校验需要人工去看对照二进制代码,量大还费力, 于是打算利用python 去调用 c++程序去校验指令, 首先要做就是用python 获取c++程序...printf() 或cout 输出; 环境linux python 3.8.x 以下代码实现,获取子程序输出 command='....linux shell指令,如果要用shell 指令ls 要将false 变成true, 通过指定stderr=subprocess.STDOUT,将子程序标准错误输出重定向到了标准输出,以使我们可以直接标准输出同时获取标准输出和标准错误信息...p.poll() 返回进程返回值,如果为None 表示 c++进程还未结束. p.stdout.readline() c++标准输出里获取一行....参考文章1 pythonsubprocess.Popen()使用 参考文章 2 python subprocess运行进程实时获取输出

    10.4K10

    2021-10-11:二叉树最大路径和。路径 被定义为一条任意节点出发,沿节点-节点连接,达到任意节点序列。同一

    2021-10-11:二叉树最大路径和。路径 被定义为一条任意节点出发,沿节点-节点连接,达到任意节点序列。同一个节点在一条路径序列 至多出现一次 。...该路径 至少包含一个 节点,且不一定经过根节点。路径和 是路径各节点值总和。给你一个二叉树根节点 root ,返回其 最大路径和 。力扣124。 福大大 答案2021-10-11: 递归。...1.1.左树整体maxsum。 1.2.右树整体maxsum。 2.有x。 2.1.只有x 2.2.x+左树路径。 2.3.x+右树路径。 2.4.x+左树路径+右树路径。。...1) 只有x 2)左树整体最大路径和 3) 右树整体最大路径和 maxPathSum := x.val if leftInfo !...(a int, b int) int { if a > b { return a } else { return b } } // 如果要返回路径做法

    1.9K20

    何在Python0到1构建自己神经网络

    在本教程,我们将使用Sigmoid激活函数。 下图显示了一个2层神经网络(注意,当计算神经网络层数时,输入层通常被排除在外。) image.png 用Python创建一个神经网络类很容易。...输入数据微调权重和偏差过程称为训练神经网络。 训练过程每一次迭代由以下步骤组成: · 计算预测输出ŷ,被称为前馈 · 更新权重和偏差,称为反向传播 下面的顺序图说明了这个过程。...image.png 前馈 正如我们在上面的序列图中所看到,前馈只是简单演算,对于一个基本2层神经网络,神经网络输出是: image.png 让我们在python代码添加一个前馈函数来做到这一点...请注意,为了简单起见,我们只显示了假设为1层神经网络偏导数。 让我们将反向传播函数添加到python代码。...总结 现在我们有了完整python代码来进行前馈和反向传播,让我们在一个例子应用我们神经网络,看看它做得有多好。 image.png 我们神经网络应该学习理想权重集来表示这个函数。

    1.8K00

    2024年3月份最新大厂运维面试题集锦(运维15-20k)

    类型注解是Python 3.5及以后版本引入特性,允许开发者为变量、函数参数和返回值指定类型。这有助于代码可读性和静态类型检查,但不强制执行类型。 58. 什么是Python字典推导式?...字典推导式是一种创建字典简洁方法,通过对序列每个元素应用表达式来生成键值对。 59. Python魔法方法是什么?...如何在Python实现单例模式?...在脚本检查并使用可用命令和工具版本。 使用条件语句处理不同环境可能差异。 72. 解释什么是Shell以及如何在Shell脚本创建它。...答案: Shell是当前Shell一个独立副本,它继承了Shell环境(变量等),但任何在Shell做出更改(变量赋值)不会影响Shell。

    2K10

    python爬虫常见面试题(一)

    一、题目部分 1、python中常用数据结构有哪些?请简要介绍一下。 2、简要描述python单引号、双引号、三引号区别。 3、如何在一个function里设置一个全局变量。...这是他们共同点。 补充:python中常见数据结构可以统称为容器(container)。序列(列表和元组)、映射(字典)以及集合(set)是三类主要容器。...变化是a指针(这里引用C概念)指向数字1变成数字2。a对象指向内存值没有发生变化,因此数字是不可变类型数据类型。字符串,元组也是同理。...,但是不会拷贝对象对象。...2、b = a.copy(): 浅拷贝, a 和 b 是一个独立对象,但他们对象还是指向统一对象(是引用)。 ?

    3.6K20

    Spark 编程指南 (一) [Spa

    ,计算所有RDD分区;在节点计算失败恢复上也更有效,可以直接计算其父RDD分区,还可以进行并行计算 RDD每个分区依赖于常数个分区(即与数据规模无关) 输入输出一对算子,且结果...RDD分区结构不变,主要是map、flatmap 输入输出一对一,但结果RDD分区结构发生了变化,union、coalesce 输入中选择部分元素算子,filter、distinct、subtract...、sample 【宽依赖】 多个子RDD分区会依赖于同一个RDD分区,需要取得其父RDD所有分区数据进行计算,而一个节点计算失败,将会导致其父RDD上多个分区重新计算 RDD每个分区依赖于所有...你可以通过--master参数设置master所连接上下文主机;你也可以通过--py-files参数传递一个用逗号作为分割列表,将Python.zip、.egg、.py等文件添加到运行路径当中;.../bin/pyspark --master local[4] 或者,将code.py添加到搜索路径(为了后面可以import): .

    2.1K10

    3.5 容错机制及依赖

    其中,1个RDD分区对应1个RDD分区,可以分为如下两种情况: ■ RDD分区与RDD分区一一对应(map、filter等算子)。...■ 一个RDD分区对应N个RDD分区(co-paritioned(协同划分)过Join)。...插图 图3-10 两种依赖关系 图3-10可以看出对依赖类型划分:根据RDD分区是对应一个还是多个子RDD分区来区分窄依赖(分区对应一个分区)和宽依赖(分区对应多个子分区)。...2)数据丢失时,对于窄依赖,只需要重新计算丢失那一块数据来恢复;对于宽依赖,则要将祖先RDD所有数据块全部重新计算来恢复。...更深入地来说:在窄依赖关系,当RDD分区丢失,重算其父RDD分区时,RDD相应分区所有数据都是RDD分区数据,因此不存在冗余计算。

    1K70

    python函数详解

    *kwargs接收全部关键字参数,聚合为字典     函数调用时,可迭代对象前加*,代表函数打散     *args,默认参数,**kwargs顺序 函数进阶: 名称空间:存储是全局(py文件...)变量与值对应关系 临时名称空间:当函数执行时,会在内存临时开辟一个空间,此空间记录函数变量与值对应关系,随着函数结束,临时名称空间而关闭 解释: Python代码运行时候遇到函数是怎么做...,Python解释器开始执行之后,就在内存开辟里一个空间,每当遇到一个变量时候,就把变量名和值之间对应关系记录下来,但是当遇到函数定义时候,解释器只是象征性将函数名读内存,表示知道这个函数存在了...等执行到函数调用时候,Python解释器会再开辟一块内存来储存这个函数里面的内容,这个时候,才关注函数里面有哪些变量,而函数变量回储存在新开辟出来内存,函数变量只能在函数内部使用,并且会随着函数执行完毕...(或者更外层作用域非全局作用域)变量进行引用和修改,并且引用哪层,从那层及以下此变量全部发生改变 3,名称空间只能引用级空间变量,但是不能修改 ?

    48530

    python面试题目及答案(数据库常见面试题及答案)

    Python没有访问说明(C ++public,private)。 在Python,函数是第一类对象。它们可以分配给变量。类也是第一类对象 编写Python代码很快,但运行比较慢。...Q13、如何在Windows上安装Python并设置路径变量?...查找路径变量,选择其值并选择“编辑”。 如果值不存在,请在值末尾添加分号,然后键入%PYTHON_HOME% Q14、python是否需要缩进? 缩进是Python必需。它指定了一个代码块。...无法解除分配C库保留那些内存部分。 退出时,由于拥有自己高效清理机制,Python会尝试取消分配/销毁其他所有对象。 Q36、Python字典是什么? Python内置数据类型称为字典。...它定义了键和值之间一对一关系。字典包含一对键及其对应值。字典由键索引。 Q37、如何在python中使用三元运算符? 三元运算符是用于显示条件语句运算符。

    11.2K20

    50道Python面试题集锦(附答案)「建议收藏」

    Python没有访问说明(C ++public,private)。 在Python,函数是第一类对象。它们可以分配给变量。类也是第一类对象 编写Python代码很快,但运行比较慢。...Q13、如何在Windows上安装Python并设置路径变量?...查找路径变量,选择其值并选择“编辑”。 如果值不存在,请在值末尾添加分号,然后键入%PYTHON_HOME% Q14、python是否需要缩进? 缩进是Python必需。它指定了一个代码块。...无法解除分配C库保留那些内存部分。 退出时,由于拥有自己高效清理机制,Python会尝试取消分配/销毁其他所有对象。 Q36、Python字典是什么? Python内置数据类型称为字典。...它定义了键和值之间一对一关系。字典包含一对键及其对应值。字典由键索引。 Q37、如何在python中使用三元运算符? 三元运算符是用于显示条件语句运算符。

    10.5K10

    用和学妹聊天时间学Python高级进阶技术——IO操作、进程和线程操作【建议收藏】

    打开文件使用内置函数 open(): f = open('文件路径', 读写模式) : f = open('/Users/obsession/text', 'w') 其中,读写模式 有以下常用选项:...序列化是将内存对象转换为可被存储或可被传输形式过程。反序列化是将序列化后内容恢复回内存对象过程。 (1)pickle Python 内置 pickle 模块用作序列化和反序列化。...或者使用 default 参数,向 json.dumps() 告知如何进行对象到字典转换,这样便可以不使用 __dict__ 属性。...json.loads() 首先会将 JSON 字符串反序列化为字典,然后使用 object_hook 参数进一步字典转换出 pair 对象。...() 获取进程进程 ID,它是进程唯一标识,可用于区分进程 使用 os.getppid() 获取进程进程 ID,进程是创建进程进程 主进程 pid 和进程 ppid 相同(因为主进程是该进程进程

    68230

    100个Python面试问题集锦

    Python适合面向对象编程,因为它允许类定义以及组合和继承。Python没有访问说明(C ++public,private)。 在Python,函数是第一类对象。它们可以分配给变量。...Q13、如何在Windows上安装Python并设置路径变量?...查找路径变量,选择其值并选择“编辑”。 如果值不存在,请在值末尾添加分号,然后键入%PYTHON_HOME% Q14、python是否需要缩进? 缩进是Python必需。它指定了一个代码块。...无法解除分配C库保留那些内存部分。 退出时,由于拥有自己高效清理机制,Python会尝试取消分配/销毁其他所有对象。 Q36、Python字典是什么? Python内置数据类型称为字典。...它定义了键和值之间一对一关系。字典包含一对键及其对应值。字典由键索引。 Q37、如何在python中使用三元运算符? 三元运算符是用于显示条件语句运算符。

    9.9K20

    Python高级进阶技术——IO操作、进程和线程操作【建议收藏】

    序列化是将内存对象转换为可被存储或可被传输形式过程。反序列化是将序列化后内容恢复回内存对象过程。 (1)pickle Python 内置 pickle 模块用作序列化和反序列化。...或者使用 default 参数,向 json.dumps() 告知如何进行对象到字典转换,这样便可以不使用 __dict__ 属性。...json.loads() 首先会将 JSON 字符串反序列化为字典,然后使用 object_hook 参数进一步字典转换出 pair 对象。...执行下: ➜ ~ python3 process.py 主进程运行 主进程 pid: 13343 进程运行 进程 pid: 13344 进程 ppid: 13343 在这里例子,...() 获取进程进程 ID,它是进程唯一标识,可用于区分进程 使用 os.getppid() 获取进程进程 ID,进程是创建进程进程 主进程 pid 和进程 ppid 相同(因为主进程是该进程进程

    81920

    SqlAlchemy 2.0 中文文档(十一)

    另请参阅 关联代理 - 允许对象和对象之间直接“多对多”样式访问,用于三类关联对象映射。...One To One 本质上是一个外键角度来看一对多关系,但表示在任何时候只会有一行指向特定行。...然后,两个独立relationship()构造首先通过一对多将侧链接到映射关联类,然后通过多对一将映射关联类链接到侧,以形成从父对象到关联对象到对象单向关联对象关系。...对于双向关系,使用四个relationship()构造将映射关联类与对象和对象在两个方向上进行链接。...另请参阅 关联代理 - 允许在三类关联对象映射中在对象和对象之间直接进行“多对多”样式访问。

    20210
    领券