資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告