数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找N叉树中最长路径的长度
假设我们有一个边列表，其中每个项目都包含 (u, v)，表示 u 是 v 的父节点。我们需要找到树中最长路径的长度。路径长度为 1 + 该路径中的节点数。
因此，如果输入类似于
则输出将为 5，因为路径为 [1, 4, 5, 7]，总共有 4 个节点，所以路径长度为 1 + 4 = 5。
为了解决这个问题，我们将遵循以下步骤：
- g := 根据给定的边列表构建图的邻接表
- d := 一个新的映射
- 定义一个函数 bfs()。它将接收 o
- d[o] := 1
- f := o
- q := [o]
- 对于 q 中的每个 x，执行以下操作：
- 对于 g[x] 中的每个 y，执行以下操作：
- 如果 y 不在 d 中，则
- d[y] := d[x] + 1
- 如果 d[y] > d[f]，则
- f := y
- 将 y 插入到 q 中
- 如果 y 不在 d 中，则
- 对于 g[x] 中的每个 y，执行以下操作：
- 返回 f
- 从主方法中，执行以下操作：
- 对于 g 中的每个 o，执行以下操作：
- f := bfs(o)
- d := 一个新的映射
- 返回 d[bfs(f)]
- 返回 0
示例
让我们看看以下实现以更好地理解：
def solve(edges):
g = {}
for u, v in edges:
if u not in g:
g[u] = []
g[u] += (v,)
if v not in g:
g[v] = []
g[v] += (u,)
d = {}
def bfs(o):
d[o] = 1
f = o
q = [o]
for x in q:
for y in g[x]:
if y not in d:
d[y] = d[x] + 1
if d[y] > d[f]:
f = y
q += (y,)
return f
for o in g:
f = bfs(o)
d = {}
return d[bfs(f)]
return 0
edges = [(1, 2),(1, 3),(1, 4),(4, 5),(5,7),(1,6),(4,8)]
print(solve(edges))输入
[(1, 2),(1, 3),(1, 4),(4, 5),(5,7),(1,6),(4,8)]
输出
5
更新于: 2021年10月19日
323 次浏览
广告