||
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]
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-13 00:21
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社