2

用 Python 编写一个算法，该算法将 prufer 代码作为输入并返回树的边缘集。输入：一个名为“p”的列表（精简代码，零索引）示例：

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

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

打印（边缘）

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

我遇到了麻烦。如何获取“p”的值，以便在“edges”中打印输出？

4

3 回答 3

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)]
于 2021-04-12T23:02:21.350 回答
0

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

在此处输入图像描述

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

在此处输入图像描述

于 2021-11-28T00:40:14.360 回答
0

David Eisenstat 的出色算法。一些挑剔：

  • .pop(0)在列表上是线性的：我希望通过用whilea替换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)]
于 2021-10-21T19:02:07.053 回答