如何从python中的字典生成图的邻接矩阵? [英] How do I generate an adjacency matrix of a graph from a dictionary in python?

问题描述

我有以下字典:

g = {
'A': ['A', 'B', 'C'], 
'B': ['A', 'C', 'E'], 
'C': ['A', 'B', 'D'],
'D': ['C','E'],
'E': ['B','D']
}

它实现一个图，每个列表包含图顶点的邻居(字典键是顶点本身).我遇到了麻烦，我想不出一种从邻居列表中获取图邻接矩阵的方法，这可能很简单，但我是python的新手，希望有人可以帮助我！我正在使用Python 3.5

It implements a graph, each list contains the neighbors of the graph vertices (dictionary keys are the vertices itself). I'm in trouble, I can not think of a way to get a graph adjacency matrix from their lists of neighbors, might be easy but I am new to python, I hope someone can help me! I am using Python 3.5

我需要生成以下矩阵:

推荐答案

没有熊猫

keys=sorted(g.keys())
size=len(keys)

M = [ [0]*size for i in range(size) ]

for a,b in [(keys.index(a), keys.index(b)) for a, row in g.items() for b in row]:
     M[a][b] = 2 if (a==b) else 1

M

[2, 1, 1, 0, 0],
[1, 0, 1, 0, 1],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 1, 0, 1, 0]]

说明

对于a，在g.items()中的行遍历key:value字典中的值，而对于b在row中的遍历值.如果我们使用(a，b)，这将给我们所有的配对.

for a, row in g.items() iterates over the key:value entries in dictionary, and for b in row iterates over the values. If we used (a,b), this would have given us all the pairs.

(keys.index(a)，keys.index(b))但是我们需要将索引分配给相应的矩阵条目

(keys.index(a), keys.index(b)) But we need the index to assign to the corresponding matrix entry,

keys = sorted(g.keys())这就是为什么我们提取并排序密钥的原因.

keys=sorted(g.keys()) that's why we extracted and sorted the keys.

a，b in ... 获取索引条目并根据对角线元素是否分配值1或2.

for a,b in... getting the index entries and assigning value 1 or 2 based on diagonal element or not.

M = [[0] *大小...... 初始化之前不能使用矩阵.

M = [ [0]*size for ... matrix cannot be used before initialization.

这篇关于如何从python中的字典生成图的邻接矩阵?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！