在 Python 中编写一个算法，它将 prufer 代码作为输入，returns 树的边集

Question

在 Python 中编写一个算法，该算法将 prufer 代码作为输入，returns 树的边集。输入：一个名为“p”的列表（prufer 代码，零索引）示例：

p = [3,1,0,0,3,2,9,9,2,3]

（可以在代码块中定义 prufer 代码。您无需编写接受用户输入的函数）输出：一个名为“边”的列表（边集_ 示例：

打印（边缘）

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

我遇到了麻烦。我怎样才能得到“p”的值，以便它在“edges”中打印输出？

Answer 1

将序列（剩余部分）中的第一个顶点连接到序列（剩余部分）中未出现的最低顶点。删除序列中的第一个顶点并重复。连接剩下的两个顶点。

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 2

David Eisenstat 的伟大算法。一些挑剔：

.pop(0) 在列表上是线性的：我更愿意通过将 while 替换为 for ... enumerate;
.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 3

下面的算法（参考this）可以在n个标记的顶点上构造出Kn的生成树，给定相应的长度为n-2的Prufer序列：

下一个代码片段实现了上述算法，以在给定 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序列调用上述函数会生成如下树，如下一个动画所示：

在 Python 中编写一个算法，它将 prufer 代码作为输入，returns 树的边集

Write an algorithm in Python which takes a prufer code as input and returns the edge set of the tree

python

algorithm

math

graph-theory

spanning-tree