prufer数列

据说这玩意什么也不算?

学,我学还不行么….

prufer数列

是一种无根树编码表示,可以解决无根树计数问题.

首先对于一颗有\(n\)个节点的无根树,他的\(prufer\)数列长度为且唯一为\(n-2\)

我们需要知道,对于\(prufer\)数列,每个点的度数是这个数出现次数+1.

我们可以根据一个数列还原出唯一的一个无根树出来.也可以根据无根树建新建一个唯一的\(prufer\)数列.

比如对于这个图

他的\(prufer\)数列为:3,5,1,3

同样的我们可以根据这个\(prufer\)数列反向解出一个无根树.


建码

我们在图中的叶子节点中找一个编号最小的节点,将与其相连的点加入\(prufer\)数列中.然后删除该节点.

模拟一下就是

在2,6,4中找到2,然后3加入数列,删除2

在4,6中找到4,然后5加入数列,删除4

在5,6中找到5,然后1加入数列,删除5

在1,6中找 谁不一样啊喂最后剩的不都是3然后删谁无所谓的啊喂 到1,然后3加入数列,删除1.

所以数列为\(3,5,1,3\)


解码

大概做法就是我们需要先构建一个集合\([1-n]\)

数列\({3,5,1,3}\),集合\({1,2,3,4,5,6}\)

我们需要先找一个未在集合中出现的点,与数列第一项相连.

即连上\({2,3}\).

数列\({5,1,3}\),集合\({1,3,4,5,6}\)

连上\({4,5}\)

数列\({1,3}\),集合\({1,3,5,6}\)

连上\({1,5}\)

数列\({3}\),集合\({1,3,6}\)

连上\({1,3}\)

数列空,集合\({3,6}\)

连上\({3,6}\)即可


By:Wahacer

2018.1.1

15:41

看我元旦还在写博客,点个爱心然后\(Accpeted\)一下呗~

发表评论

电子邮件地址不会被公开。 必填项已用*标注