首页
学习
活动
专区
工具
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、解决方案有几种方法可以存储字典中值的路径。第一种方法是使用循环。我们可以使用一个循环来遍历路径中的每个键,然后使用这些键来获取值。...第三种方法是使用自定义字典类。我们可以创建一个自己的字典类,并在其中定义一个新的方法来获取值的路径。

9510

【从零学习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部分组成,键:值。

12910
  • 【从零学习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 =

    13310

    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 python中的subprocess.Popen()使用 参考文章 2 python 从subprocess运行的子进程中实时获取输出

    10.5K10

    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

    如何在Python中从0到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。

    3.1K10

    python爬虫常见面试题(一)

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

    3.8K20

    爬虫工程师面试题

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

    9310

    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.3K20

    用和学妹聊天的时间学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 相同(因为主进程是该子进程的父进程

    68430

    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

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

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

    10.6K10

    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 相同(因为主进程是该子进程的父进程

    84720
    领券