公开(公告)号：CN110347880A

公开(公告)日：2019-10-18

申请号：CN201910526974.6

申请日：2019-06-18

Applicant: 广州大学

Inventor： 李乙侠 ,  李树栋 ,  吴晓波 ,  韩伟红 ,  方滨兴 ,  田志宏 ,  殷丽华 ,  陈燕珊 ,  卢丹娜 ,  王薇 ,  郑敏真 ,  何沛言 ,  顾钊铨 ,  仇晶 ,  李默涵 ,  唐可可

IPC: G06F16/901 ,  G06F16/906

Abstract: 本发明公开了一种最大连通子图尺寸的快速计算方法，包括：S1，设置包含n个节点的图G的最短距离矩阵Dn×n；S2，根据变换公式将最短距离矩阵Dn×n变换为可达矩阵An×n；S3，将可达矩阵An×n的向量根据预设分类规则分为k类，其中将每类中向量的行列数作为容量ik，k≥1；S4，根据每类容量ik的最大值判别出最大连通子图的尺寸。本方案通过利用最短距离矩阵来获得可达矩阵，并直接从可达矩阵中识别最大连通尺寸，避免了传统的最大连通子图尺寸计算需要遍历需遍历所有节点，本方案不仅减少了复杂的计算，还便于实现。