Python의 n-ary 트리에서 가장 긴 경로의 길이를 찾는 프로그램

<시간/>

각 항목이 보유하고 있는 에지 목록이 있다고 가정합니다. (u, v)는 u가 v의 부모임을 나타냅니다. 트리에서 가장 긴 경로의 길이를 찾아야 합니다. 경로 길이는 1 + 해당 경로의 노드 수입니다.

따라서 입력이 다음과 같으면

경로가 [1, 4, 5, 7]이기 때문에 출력은 5가 되고 총 4개의 노드가 있으므로 경로 길이는 1 + 4 =5입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

g :=주어진 에지 목록에서 그래프의 인접 목록
d :=새 지도
bfs() 함수를 정의합니다. 시간이 걸립니다
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
    - q에 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)]