<p>可能不是最有效的,但是一种简单的方法可以将格式转换为列表形式的邻接矩阵,如下所示:</p>
<pre><code>g = {1:{2:.5, 3:.2}, 2:{4:.7}, 4:{5:.6, 3:.3}}
hubs = g.items() # list of nodes and outgoing vertices
size=max(map(lambda hub: max(hub[0], max(hub[1].keys())), hubs))+1 # matrix dimension is highest known node index + 1
matrix=[[None]*size for row in range(size)] # set up a matrix of the appropriate size
for node, vertices in hubs: # loop through every node in dictionary
for vertice, weight in vertices.items(): # loop through vertices
matrix[vertice][node] = weight # define adjacency of both nodes by assigning the vertice's weight
</code></pre>
<p>这适用于有向图,假设节点仅由以零开头的索引表示。以下是此示例中处理的图形的可视化和结果矩阵:</p>
<p><img src="https://i.stack.imgur.com/oBNMt.png" alt=""/></p>
<pre><code> 0 1 2 3 4 5
------------------------------
0 |
1 |
2 | 0.5
3 | 0.2 0.3
4 | 0.7
5 | 0.6
</code></pre>
<p>如果你的图实际上是无向的,我可以考虑一些优化的机会。如果字典将每个节点作为键包含,并列出其所有顶点,如<code>{1:{2:.2, 3:.3}, 2:{1:.2}, 3:{1:.3}}</code>,则可以在遍历前对相应列表进行排序,并限制内部循环:</p>
<pre><code>hubs = sorted(g.items())
for node, vertices in hubs:
for vertice, weight in reversed(sorted(vertices.items())):
if vertice >= node:
matrix[vertice][node] = weight
matrix[node][vertice] = weight
else: # do only care about vertices that haven't been saved before,
break # continue with next node when the current one won't introduce any more vertices
</code></pre>
<p>使用<a href="http://docs.python.org/2/library/bisect.html" rel="nofollow noreferrer">binary search</a>可能会更有效。由于得到的矩阵显然是镜像对称矩阵,所以您也可以进一步,只存储其中的一半。最简单的方法是在垂直轴上翻转:</p>
<pre><code># unlike the one before, this sample doesn't rely on the dictionary containing every vertice twice
matrix=[[None]*size for row in range(size)]
for node, vertices in hubs:
for vertice, weight in vertices.items():
matrix[vertice][size-node-1] = weight
</code></pre>
<p>由于矩阵的一半被切断,并非每次查找节点<code>(u,v)</code>之间的垂直都能工作,因此必须确保列的索引大于要查找的单元格的行的索引:</p>
<pre><code>u,v = sorted((u,v))
weight = matrix[v][u]
</code></pre>
<p>祝你好运!</p>