【ROSALIND】【练Python，学生信】32 构建一棵树

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

构建一棵树（Completing a Tree）

Given: A positive integer n (n≤1000) and an adjacency list corresponding to a graph on n nodes that contains no cycles.

所给：一个不大于1000的正整数n以及一个邻接表，对应一个有n个结点且无环的图。

Return: The minimum number of edges that can be added to the graph to produce a tree.

需得：添加到图中从而构成树的边的最小数目。

 

测试数据

10

1 2

2 8

4 10

5 9

6 10

7 9

测试输出

3

 

生物学背景

        进化树是进化生物学中用来表示物种进化关系的图表。从进化树中我们可以读出物种间的进化关系和距离。

 

数学背景

        所谓无向图就是边没有方向，相连两个点可以互相抵达的图。树则是不含环的无向图，结构与自然界中的相对应，如下所示：

        无向图顶点的边数称为度（degree），度为1的结点为叶子结点，度大于1的结点为内节点。

        邻接表是数组与链表相结合的存储方法。本题中所给的邻接表每行给出的两个数字代表两个结点由边相连。

 

思路

        由给出的示例数据可以画出下图：

        从绘图结果很容易看出，这十个结点形成了四“堆”：

只需要添加三条边就可以变成一棵树。

        示例所给的数据比较简单，但对复杂数据，原理是相同的，请详见代码注释。

代码

f = open('input.txt', 'r')
lines = f.readlines()
f.close()

num = lines[0] # 存储结点的数目
edges = lines[1:] # 存储边的关系
i = 1
nodes = []
while i <= int(num):
    nodes.append(str(i)) # 用一个列表保存所有节点
    i += 1

fedge = edges[0].replace('\n','') # 把邻接表第一行取出来，作为第一“堆”的基础
fedge = fedge.split(' ')
nodes.remove(fedge[0])
nodes.remove(fedge[1])
tree = [fedge] # tree用来存储结点通过邻接表存储的关系形成的“堆”
flag = 1 # flag存储现在tree里有几“堆”
i = 1
while i < len(edges): # i遍历邻接表
    edge = edges[i].replace('\n','')
    edge = edge.split(' ')
    if edge[0] in nodes:
        nodes.remove(edge[0]) # 每取出一个边，就把形成边的结点从结点列表中删去
    if edge[1] in nodes:
        nodes.remove(edge[1])
    j = 0
    tag = 0
    note = []
    while j < flag: # j用来遍历各“堆”
        if edge[0] in tree[j]: # 如果这条边的一个结点已经在其中一个“堆”里
            tree[j].append(edge[1]) # 把这个边加入这一“堆”
            tag += 1
            note.append(j) # note存储这个结点在哪个“堆”
            j += 1
        elif edge[1] in tree[j]:
            tree[j].append(edge[0])
            tag += 1
            note.append(j)
            j += 1
        else: # 如果不在这一“堆”里，j加一，以查找下一“堆”
            j += 1
    if tag == 0: # 如果在之前存在的“堆”里都没有这条边
        tree.append(edge)
        flag += 1 # 添加一个新的“堆”
    if tag == 2: # 如果两个结点各在两“堆”中，说明这两个“堆”可以合并
        flag -= 1
        tree[note[0]].extend(tree[note[1]])
        tree.remove(tree[note[1]]) # 合并两“堆”并删去其中一个
        tree[note[0]].remove(edge[0])
        tree[note[0]].remove(edge[1]) # 删去由合并导致的重复结点

    i += 1

print(tree)
lennodes = len(nodes) # 记录现在结点列表中还有几个结点，每个都相当于一个单独的“堆”
sum = (flag - 1) + lennodes # “堆”的数量减去一即为需要添加的边的数量
print(sum)