Python 结构体随机生成树
时间: 2023-08-14 14:13:30 浏览: 52
生成随机树的常用算法是Prim算法和Kruskal算法,它们都可以用来生成带权的树,也可以用来生成无权的树。这里以Prim算法为例,介绍如何在Python中生成随机无权树的代码:
```python
import random
# 定义节点类
class Node:
def __init__(self, val):
self.val = val
self.neighbours = []
# 定义生成随机树的函数
def generate_random_tree(n):
nodes = [Node(i) for i in range(n)] # 创建节点列表
root = nodes[0] # 随机选取一个节点作为根节点
visited = {root} # 标记已经访问的节点
unvisited = set(nodes[1:]) # 未访问的节点集合
while unvisited:
# 随机选择一个已经访问的节点和一个未访问的节点
v = random.choice(list(visited))
u = random.choice(list(unvisited))
# 将u加入到v的邻居列表中,并标记u已经访问
v.neighbours.append(u)
visited.add(u)
unvisited.remove(u)
return root
# 测试代码
if __name__ == '__main__':
root = generate_random_tree(10)
print(root.val)
print([node.val for node in root.neighbours])
```
这段代码中,我们首先定义了一个节点类,每个节点有一个值和一个邻居列表。然后定义了一个生成随机树的函数,函数的输入是节点个数n,输出是随机生成的树的根节点。在函数中,我们首先创建节点列表,然后随机选取一个节点作为根节点,并将其标记为已经访问。然后我们维护两个集合,一个是已经访问的节点集合visited,一个是未访问的节点集合unvisited。在每一次循环中,我们随机选择一个已经访问的节点v和一个未访问的节点u,将u加入到v的邻居列表中,并将u标记为已经访问。最后返回根节点即可。
以上代码仅给出了一个简单的无权树的生成算法,如果需要生成带权树,可以在每次选择未访问节点时,随机赋予一个权值。