Dini的个人博客分享 http://blog.sciencenet.cn/u/Dini

博文

邻接矩阵怎么变成二维网格啊?

已有 1047 次阅读 2019-10-7 19:40 |个人分类:|系统分类:科研笔记

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]  




http://blog.sciencenet.cn/blog-3411101-1200982.html

上一篇:Java冒泡排序法
下一篇:加权网络的边介数

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-1-27 06:42

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部