怎样用python对邻接矩阵进行标准化处理(出度)

总是学不会儿 发布于 10/12 08:37
阅读 204
收藏 0

怎样用python对邻接矩阵进行标准化处理(出度)

加载中
0
tcxu
tcxu

参考:Python 数据结构与算法——图出度和入度的计算,

楼主只需自己 添加一个 把 邻接矩阵转换为邻接集的方法, 就能完工。 

其中邻接集的字典数据有误。正确的邻接集字典数据、邻接矩阵如下:

# 邻接矩阵
AdjMatrix =[
        [0, 1, 1, 1, 1, 1, 0, 0],  # a
        [0, 0, 1, 0, 1, 0, 0, 0],  # b
        [0, 0, 0, 1, 0, 0, 0, 0],  # c
        [0, 0, 0, 0, 1, 0, 0, 0],  # d
        [0, 0, 0, 0, 0, 1, 0, 0],  # e
        [0, 0, 1, 0, 0, 0, 1, 1],  # f
        [0, 0, 0, 0, 0, 1, 0, 1],  # g
        [0, 0, 0, 0, 0, 1, 1, 0]  # h
    ]
for x in AdjMatrix:
    for y in x:
        print(y,end=' ')
    print()
# 邻接集的字典
G = { 'a':set('bcdef'),
      'b':set('ce'),
      'c':set('d'),
      'd':set('e'),
      'e':set('f'),
      'f':set('cgh'),
      'g':set('fh'),
      'h':set('fg') }

out_degrees = dict((u, 0) for u in G)
in_degrees = dict((u, 0) for u in G)
for u in G:
    out_degrees[u] = len(G[u])
for u in G:
    for v in G[u]:
        in_degrees[v] += 1
print(out_degrees)
print(in_degrees)

输出:

0 1 1 1 1 1 0 0 
0 0 1 0 1 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 1 1 
0 0 0 0 0 1 0 1 
0 0 0 0 0 1 1 0 
{'a': 5, 'b': 2, 'c': 1, 'd': 1, 'e': 1, 'f': 3, 'g': 2, 'h': 2}
{'a': 0, 'b': 1, 'c': 3, 'd': 2, 'e': 3, 'f': 4, 'g': 2, 'h': 2}

 

0
tcxu
tcxu

用 python,已知邻接矩阵 (对应楼上的图),求 1.出度, 2.入度。

# 邻接矩阵
AdjMatrix =[
        [0, 1, 1, 1, 1, 1, 0, 0],  # a
        [0, 0, 1, 0, 1, 0, 0, 0],  # b
        [0, 0, 0, 1, 0, 0, 0, 0],  # c
        [0, 0, 0, 0, 1, 0, 0, 0],  # d
        [0, 0, 0, 0, 0, 1, 0, 0],  # e
        [0, 0, 1, 0, 0, 0, 1, 1],  # f
        [0, 0, 0, 0, 0, 1, 0, 1],  # g
        [0, 0, 0, 0, 0, 1, 1, 0]  # h
    ]
vertex=['a','b','c','d','e','f','g','h']

def outDegree(mat, name):
    print('出度:')
    i=0
    for x in mat:
        degree=0
        for y in x:
            if y==1:
                degree = degree + 1
        print(name[i] ,'出度:',degree, end=', ')
        i=i+1

def intDegree(mat, name):
    print('\n入度:')
    for i in range(0, len(mat)):
        degree=0
        for j in range(0, len(mat)):
            if mat[j][i]==1:
                degree = degree + 1
        print(name[i], '入度:',degree, end=', ')

outDegree( AdjMatrix, vertex )
intDegree( AdjMatrix, vertex )

输出:

D:\untitled\venv\Scripts\python.exe D:/pythonProject0/out_int_Degree.py
出度:
a 出度: 5, b 出度: 2, c 出度: 1, d 出度: 1, e 出度: 1, f 出度: 3, g 出度: 2, h 出度: 2, 
入度:
a 入度: 0, b 入度: 1, c 入度: 3, d 入度: 2, e 入度: 3, f 入度: 4, g 入度: 2, h 入度: 2, 

 

返回顶部
顶部