什么是Prufer序列？
在组合数学中， Prufer序列是一种编码树结构的方法，从树中生成唯一的序列。 Prufer序列通常用于将树编码为一种不同于树的方式，以便更容易地进行处理。它的主要用途是计算生成树的数量，以及解决与树相关的其他问题。Prufer序列由翁加佳·普鲁夫尔（Wolfgang Prüfer）于1918年引入。
如何生成Prufer序列？
1. 基本思路
生成Prufer序列的基本思路是，从一棵树开始，重复执行以下步骤，直到树中只剩下两个节点：
步骤1：找到叶子节点中编号最小的一个（编号从1开始）。
步骤2：将该叶子节点的父节点的编号写入Prufer序列中。
步骤3：删除该叶子节点。
重复以上步骤，直到只剩下两个节点。Prufer序列中剩下的两个数字就是树中最后剩余的两个节点的编号。
2. 算法流程
以下是生成Prufer序列的算法流程：
vector<int> prufer(vector<int>& tree)
{
int n = tree.size() + 2;
vector<int> degree(n, 1);
for (int i = 0; i < tree.size(); i++)
{
degree[tree[i]]++;
}
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i < n; i++)
{
if (degree[i] == 1)
{
pq.push(i);
}
}
vector<int> res(n - 2);
for (int i = 0; i < n - 2; i++)
{
int x = pq.top();
pq.pop();
res[i] = tree[x - 1];
degree[tree[x - 1]]--;
if (degree[tree[x - 1]] == 1)
{
pq.push(tree[x - 1]);
}
}
return res;
}
这个算法使用优先队列来存储所有叶子节点的编号，并按照编号从小到大的顺序依次选取叶子节点。在选取一个叶子节点后，需要将该节点与其对应的父节点的度数减1，并将新的叶子节点加入队列中。
如何打印Prufer序列中每个节点的度数？
生成Prufer序列的同时，也可以统计每个节点的度数（即与该节点相邻的节点的个数）。具体来说，我们可以使用一个vector存储每个节点的度数，初始化时将每个节点的度数设置为1。然后在选择一个叶子节点时，将其对应的父节点的度数减1。最后，剩余的两个节点的度数分别为1和2。
以下是打印Prufer序列中每个节点的度数的代码：
vector<int> prufer(vector<int>& tree, vector<int>& degree)
{
int n = tree.size() + 2;
for (int i = 0; i < tree.size(); i++)
{
degree[tree[i]]++;
}
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i < n; i++)
{
if (degree[i] == 1)
{
pq.push(i);
}
}
vector<int> res(n - 2);
for (int i = 0; i < n - 2; i++)
{
int x = pq.top();
pq.pop();
res[i] = tree[x - 1];
degree[tree[x - 1]]--;
if (degree[tree[x - 1]] == 1)
{
pq.push(tree[x - 1]);
}
}
return res;
}
在返回Prufer序列的同时，该函数还会返回存储每个节点度数的vector。
总结
Prufer序列是一种编码树结构的方法，可以很方便地进行树的处理。通过遍历树并使用优先队列进行叶子节点的选择，我们可以非常高效地生成Prufer序列，同时统计每个节点的度数。Prufer序列在组合数学中有很多应用，尤其是计算生成树的数量。