Prüfer sequence - Labeled Tree 인코딩/디코딩

N개 노드로 이루어진 Labeled Tree가 있을 때, N-2 사이즈의 유일한 Prüfer sequence를 항상 얻을 수 있다.

또 Prüfer sequence를 해독해서 다시 Tree로 만들 수도 있다. 즉, Tree 자체를 인코딩/디코딩하는 알고리즘 

https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

Prüfer sequence - Wikipedia

1. Labeled Tree → Prüfer sequence

'작은 label' (이 조건 중요)의 leaf부터 제거하면서, leaf의 parent를 기록하면 끝. 노드 2개 남을 때 까지 반복

 

2. Prüfer sequence → Labeled Tree

N개 노드의 degree를 먼저 구한다. 

1로 모두 초기화 한 뒤, Prufer seq에 기록된 노드들에는 1씩 더해준다 (leaf를 제거하면서 parent를 기록한거니까!)

degree = [1]*(N+1)
for node in prufer_seq:
    degree[node] += 1

 

이제, 'degree 값이 1인 노드 = original tree에서의 leaf노드' 라는 것을 알 수 있다.

이 leaf노드들을 Prufer seq에 등장한 parent node에 하나씩 붙여주기만 하면 된다.

 

원래 Tree를 복원하기 위해선 붙이는 순서가 중요한데, 작은 label을 가지는 leaf노드부터 붙여주면 된다 (Tree를 Prufer seq로 인코딩할 때, 작은 label부터 제거하는 이유)

# 2중 for-loop 써서 매번 deg에서 leaf node 찾아도 되지만, pq를 쓸 수도 있다!

pq = [] # keep nodes with deg 1 (leaf nodes)
for idx, deg in enumerate(degree):
    if idx > 0 and deg == 1:
        heapq.heappush(pq, idx) # push leaf nodes into PQ

original_tree = []
for parent in prufer_seq:
    leaf = heapq.heappop(pq)
    original_tree.append((leaf, parent))
    degree[leaf] -= 1
    degree[parent] -= 1
    if degree[parent] == 1:
        heapq.heappush(pq, parent)

 

Tree 관련된 알고리즘으로 알아두면 좋을 것 같다.

 

+ Cayley's formula의 증명에 사용됨

https://en.wikipedia.org/wiki/Cayley%27s_formula

 

 

LeetCode 문제 풀다가 처음 발견

https://leetcode.com/problems/redundant-connection/discuss/107987/A-completely-difference-approach%3A-recursively-remove-leaf-nodes-to-uncover-the-cycle-in-the-graph

A completely difference approach: recursively remove leaf nodes to uncover the cycle in the graph - LeetCode Discuss