import random

import networkx as nx

"""

Wilson 一致生成树算法:

这个算法的关键概念是 LERW (loop erased random walk).

1. 从图 G 中任选一个顶点 v, 维护一个树 T, 初始时刻 T = {v}.

2. 从任一不属于 T 的顶点 u 出发作随机游动, 直到这个游动与 T 相遇为止, 

   设经过的路径为 p, 将 p 中的回路都擦除, 得到一条无回路的路径 q=LERW(q), 将路径 q 加入到 T 中.

3. 重复以上步骤直到 G 的所有顶点均属于 T 为止, 这时得到的 T 就是一颗一致生成树.

"""

n = input('Enter grid size: ')

G=nx.grid_2d_graph(n,n)                          这里我想读入自己的网络邻接矩阵文件，怎么变成二维网格呢？

nx.grid_2d_graph这个用法看不懂啊！

root = random.choice(G.nodes()) #任选一个顶点作为根节点

tree = set([root]) 

parent = dict() 

for vertex in G.nodes(): # 对 G 的每个顶点

    v = vertex

    while v not in tree: # 只要它还不在生成树内 

        neighbor = random.choice(G.neighbors(v)) # 任选其一个相邻顶点

        parent[v] = neighbor  # 记录下走的路径

        v = neighbor # 并且走到这个新顶点. 注意如果过程中出现绕了一个圈又回到某个顶点 v 的情形, 则 parent[v] 会更新为新的路径, 即沿着 v-->parent[v] --> ....行走, 圈是被跳过去的, 这就是擦圈!

    v = vertex

    while v not in tree:

        tree.add(v)   

        v = parent[v]