用 Python 编写程序，用于查找 n 叉树中最长路径的长度
pythonserver side programmingprogramming更新于 2026/1/23 5:00:17
假设我们有一个边列表，其中每个项目都包含 (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
- 从 main 方法中，执行以下操作 −
- 对于 g 中的每个 o，执行
- f := bfs(o)
- d := a new map
- 返回 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
