首页 > 代码库 > 传递闭包
传递闭包
传递闭包:
有向图的传递闭包表示的就是两个顶点之间的可达性
将有向图化为布尔矩阵,两点有边相连为 1,否则为 0
布尔矩阵 B 自乘 N 次,进行布尔运算得到B(N)
B(N)[i][j]意义是,能否经过 N 长度的路径从 i --> j
而将中间过程的产生的一系列 B 经行布尔运算叠加得到的最后矩阵 M
就是该图中的任意两点是否可达的信息,即M[i][j] == 1,则意味着 i --> j 可达
import numpy A0 = numpy.array( [ [False, True, False, False], [False, False, False, True], [False, False, False, False], [True, False, True, False] ] ) print 'A0:' print A0 A1 = numpy.dot( A0, A0 ) | A0 print 'A1:' print A1 A2 = numpy.dot( A0, A1 ) | A1 print 'A2:' print A2 A3 = numpy.dot( A0, A2 ) | A2 print 'A3:' print A3 A4 = numpy.dot( A0, A3 ) | A3 print 'A4:' print A4 A5 = numpy.dot( A0, A4 ) | A4 print 'A5:' print A5
A0: [[False True False False] [False False False True] [False False False False] [ True False True False]] A1: [[False True False True] [ True False True True] [False False False False] [ True True True False]] A2: [[ True True True True] [ True True True True] [False False False False] [ True True True True]] A3: [[ True True True True] [ True True True True] [False False False False] [ True True True True]] A4: [[ True True True True] [ True True True True] [False False False False] [ True True True True]] A5: [[ True True True True] [ True True True True] [False False False False] [ True True True True]]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。