生成连通无向图脚本

Question

我正在尝试用Python 2.7创建一个有连接的、间接的图，并且每条边都有权重。以下是我目前写的脚本。

for i in xrange(0, 10):
    for j in xrange(0, (int)(10*random.random())):
        lst2 = random.sample(range(20), 1)
        j = [(i, lst2)]
        print(j)

我想要的格式是：x y w，其中(x,y)表示一个顶点，w是权重。目前我能生成随机数量的x，这正是我想要的，但在生成y的时候遇到了一些问题，尤其是我想避免重复的顶点，比如(1,3)和(3,1)被认为是同一个顶点。下面是我当前输出的一小部分。

   [(1, [6])]
[(1, [1])]
[(1, [15])]
[(1, [12])]
[(1, [16])]
[(2, [9])]
[(3, [10])]
[(3, [19])]
[(4, [17])]
[(4, [18])]
[(4, [17])]

我该如何避免顶点重复，同时又能随机生成x的数量呢？另外，我该如何添加权重？我试过一些方法，但结果只是生成了多余的配对。

for i in xrange(0, 10):
    for j in xrange(0, (int)(10*random.random())):
        lst2 = random.sample(range(20), 1)
        lst3 = random.sample(range(10), 10)
        j = zip((i, lst2),lst3)
        print(j)

Answer 1

你可以这样做：

import random

nodeCount = 6
vertexCount = 10

vertices = {}
while len(vertices) < vertexCount:
    x = random.randint (1, nodeCount)
    y = random.randint (1, nodeCount)
    if x == y: continue
    #comment the following line if the graph is directed
    if y < x: x, y = y, x
    w = random.random ()
    vertices [x, y] = w

#just for debug
for (x, y), w in vertices.items ():
    print ('Vertex from {} to {} with weight {}.'.format (x, y, w) )