用Python编写一个算法，该算法以prufer代码作为输入，并返回树的边缘集

Question

用Python编写一个算法，该算法以prufer代码作为输入，并返回树的边缘集。输入:一个名为"p“的列表( prufer代码，零索引)示例：

P= 3,1,0,0,3,2,9,9,2,3

( prufer代码可以在代码块中定义。您不需要编写接受用户输入的函数的输出:名为“边缘”的列表( edge set_示例：

打印(边)

[3、4、1、5、0、1、0、6、3、0、2、7、9、8、9、10、2、9、3、2、3、11]

我在这件事上有麻烦。如何才能得到"p“的值，以便在”边“中打印输出？

Answer 1

伟大的算法大卫艾森特。一些挑剔的人：

• .pop(0)对列表是线性的:我更倾向于通过用for ... enumerate替换while来使列表遍历更加显式；
• .difference()不需要将第二个操作数转换为一个集合；
• min()和max()有点过火，因为我们知道剩下的集合正好有两个元素。

def decode(p):
    p = list(p)
    vertices = set(range(len(p) + 2))
    for (i, u) in enumerate(p):
        v = min(vertices.difference(p[i:]))
        vertices.remove(v)
        yield u, v
    yield tuple(vertices)


print(list(decode([3, 1, 0, 0, 3, 2, 9, 9, 2, 3])))

输出：

[(3, 4), (1, 5), (0, 1), (0, 6), (3, 0), (2, 7), (9, 8), (9, 10), (2, 9), (3, 2), (3, 11)]

Answer 2

将序列中的第一个顶点连接到序列中没有出现(剩馀的)的最低顶点。删除序列中的第一个顶点并重复。连接剩下的两个顶点。

def decode(p):
    p = list(p)
    vertices = set(range(len(p) + 2))
    while p:
        v = min(vertices - set(p))
        vertices.remove(v)
        yield p.pop(0), v
    yield min(vertices), max(vertices)


print(list(decode([3, 1, 0, 0, 3, 2, 9, 9, 2, 3])))

输出：

[(3, 4), (1, 5), (0, 1), (0, 6), (3, 0), (2, 7), (9, 8), (9, 10), (2, 9), (3, 2), (3, 11)]

Answer 3

下面的算法(参考这)可用于构造n个标号顶点上的Kn生成树，并给出相应的长度为n-2的Prufer序列：

​

​

下一个代码段实现了上述算法，通过计算边缘生成一个标记树(还注意到我们在python中有基于零的索引)：

def get_tree(S):
    n = len(S)
    L = set(range(n+2))
    tree_edges = []
    for i in range(n):
        u, v = S[0], min(L - set(S))
        S.pop(0)
        L.remove(v)
        tree_edges.append((u,v))
    tree_edges.append((L.pop(), L.pop()))
    return tree_edges

调用输入Prufer序列上的上述函数将生成以下树，如下一个动画所示：

​

​