首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在python中从字典中生成图的邻接矩阵?

问如何在python中从字典中生成图的邻接矩阵?
EN

Stack Overflow用户
提问于 2016-05-21 02:42:16
回答 3查看 13.1K关注 0票数 2

我有一本字典:

代码语言:javascript
复制
g = {
'A': ['A', 'B', 'C'], 
'B': ['A', 'C', 'E'], 
'C': ['A', 'B', 'D'],
'D': ['C','E'],
'E': ['B','D']
}

它实现了一个图,每个列表包含图顶点的邻居(字典键是顶点本身)。我遇到麻烦了,我想不出一种方法来从他们的邻居列表中获得图邻接矩阵,可能很容易,但我是python的新手,我希望有人能帮助我!我使用的是Python 3.5

我需要生成以下矩阵:

​

​

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2016-05-21 03:25:19

没有熊猫

代码语言:javascript
复制
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]]

说明

for a, row in g.items()遍历字典中的key:value条目,for b in row遍历这些值。如果我们使用(a,b),这将给我们所有的对。

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

keys=sorted(g.keys()),这就是我们提取和排序关键字的原因。

for a,b in...获取索引项,并根据对角线元素或非对角线元素赋值1或2。

在初始化之前不能使用M = [ [0]*size for ...矩阵。

票数 6
EN

Stack Overflow用户

发布于 2016-05-21 02:58:18

这是一个使用pandas的解决方案。

代码语言:javascript
复制
import pandas as pd

g = {
'A': [ 'A', 'B', 'C'], 
'B': [ 'A', 'C', 'E'], 
'C': [ 'A', 'B ',' D '], # I added a comma here
'D': [' C ',' E '],
'E': [' B ',' D ']
}

# clean up the example
g = {k: [v.strip() for v in vs] for k, vs in g.items()}

edges = [(a, b) for a, bs in g.items() for b in bs]

df = pd.DataFrame(edges)

adj_matrix = pd.crosstab(df[0], df[1])

# 1  A  B  C  D  E
# 0               
# A  1  1  1  0  0
# B  1  0  1  0  1
# C  1  1  0  1  0
# D  0  0  1  0  1
# E  0  1  0  1  0

我不知道为什么你的示例矩阵中的(A,A)位置有2。

票数 6
EN

Stack Overflow用户

发布于 2019-07-01 07:26:49

代码语言:javascript
复制
import numpy as np
mat = np.zeros(shape = (len(g), len(g)))
for k, vs in g.items():
    for v in vs:
        if v in g[k]:
            mat[k][v] = 1
票数 -1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/37353759

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档