生成二维网格约束的随机连通无环图及代码错误修复求助

1. 直接报错原因修复 #

你遇到的object of type 'generator' has no len()错误，根源是这行代码：

thx,thy = choice(path[j] for j in range(len(path)))

这里的path[j] for j in range(len(path))是生成器对象，而random.choice()需要传入具备长度属性的序列（比如列表、元组）。完全没必要通过索引遍历生成元素，直接用choice(path)就能随机选取path里的任意坐标点，修改后这行变为：

thx, thy = choice(path)

2. 原逻辑的缺陷修正 #

原代码碰到新生成的坐标已在路径中时直接返回，会导致生成的树提前终止（可能远达不到你指定的100000个节点），而且无法保证生成完整的连通无环图。正确的逻辑应该是：

• 每次从已有的节点中随机选一个
• 遍历它的四个方向邻居，筛选出未被访问过的节点
• 如果有可用邻居，随机选一个加入路径；如果没有，就重新选其他节点继续尝试，直到添加够指定数量的节点

3. 完整改进代码 #

from random import choice
from matplotlib import pyplot as plt
plt.style.use('seaborn-v0_8-darkgrid')

def random_grid_tree(n):
    # 初始化起点和已访问节点集合
    path = [(0, 0)]
    visited = set(path)
    
    while len(path) < n + 1:  # 初始已有1个节点，n为需要新增的节点数
        # 随机选一个已存在的节点
        current_x, current_y = choice(path)
        # 生成四个方向的邻居
        neighbors = [
            (current_x + 1, current_y),
            (current_x - 1, current_y),
            (current_x, current_y + 1),
            (current_x, current_y - 1)
        ]
        # 筛选未被访问的邻居
        unvisited_neighbors = [pos for pos in neighbors if pos not in visited]
        if unvisited_neighbors:
            # 随机选一个未访问邻居加入
            new_pos = choice(unvisited_neighbors)
            path.append(new_pos)
            visited.add(new_pos)
    
    return path

def show_path(path):
    plt.figure(figsize=(10, 10))
    plt.scatter(*zip(*path), s=5, c='k')
    plt.plot(*zip(*path), c='r')
    plt.show()

# 生成包含100001个节点的树（n=100000表示添加100000个新节点）
path = random_grid_tree(100000)
show_path(path)

代码说明 #

• 用visited集合来快速判断节点是否已存在（比列表的in操作效率高得多，适合大数量节点场景）
• 循环直到路径长度达到指定数量，不会提前终止
• 每次仅扩展未访问的邻居，保证生成的图无环且连通（符合树的定义）

内容的提问来源于stack exchange，提问作者summersfreezing