基于K²-MDD的大规模图的最大公共连通子图匹配方法

摘要

本发明公开一种基于K²‑MDD的大规模图的最大公共连通子图匹配方法，首先对两个图中的顶点进行编码，再根据顶点的编码再对边编码，进而通过边的编码集合构建K²‑MDD；之后利用符号K²‑MDD的逻辑交运算求出每个顶点的度，将度最大的顶点纳入公共子图中，并把与之相邻顶点的度减1，直至相邻边的顶点度全部为0，实现对最大公共连通子图的求解。本发明用K²树的思想对邻接矩阵进行划分，然后使用多值决策图进行存储，使K²树中大量的同构子树所造成的冗余顶点得到合并，达到存储结构更为紧凑的目的，大大减少了顶点产生数量，从而减少了搜索空间，也提高了搜索效率。