一种基于距离矩阵的最大连通子图评估方法及系统

摘要

本发明提供了一种基于距离矩阵的最大连通子图评估方法，包括：根据图的邻接矩阵用Dijkstra方法计算距离矩阵，并预估类别数的最大值以合理分配存储空间，然后初始化最大连通子图和其余连通子图，搜索剩余节点对应的行，并进行分类，计算节点个数，与最大连通子图比较，保留节点数较多的子图，相同则都保存，当后续出现的连通子图比先前保留的多个子图更多节点的时，则删除已存放的子图；已经被分类的剩余节点则跳过搜索，减少循环次数。本发明将求最大连通子图的规模问题转化为分类问题，节省存储空间，有利于解决节点数过大计算效率过于低下的图论问题。