技术摘要：
本申请提供了一种基于图的多点路径查询方法，接收到查询请求时，针对V中的每个起始顶点扩展M层，将每个起始顶点分别记录到一个数组中；将V中的两两起始顶点对应的扩展信息求交集之后，再将所有交集内的扩展信息求并集；并获取并集中前N条扩展信息作为初步扩展信息；根  全部
背景技术：
图(Graph)是用来表示物件与物件之间的关系的对象，是图论的基本研究对象。图 是一个有序二元组(V,E)，其中V称为顶点集，E称为边集。E的元素用(x,y)表示，其中x,y∈ V。 计算图中多个顶点之间的关系是非常有意义的，例如：计算两个人在网络上的人 脉关系，计算多家公司的之间的投资关系等。 传统计算方法为：以一个节点为中心向外层扩展，直到扩展到目的节点或者达到 限定的层次为止。 由一个顶点向外层扩展时，随着扩展计算层次的增加，计算的节点会形成指数级 的增加，所以该计算方式不仅效率低，而且对内存消耗比较大。 如：假设图中的每个顶点与100个顶点存在直接关系，如果要遍历该顶点的2层关 系，就涉及到100的2次方，也就是10000个顶点数据的加载。如果计算6层关系，就会加载1万 亿个顶点数据。
技术实现要素：
有鉴于此，本申请提供一种基于图的多点路径查询方法和装置，能够提高查询效 率。 为解决上述技术问题，本申请的技术方案是这样实现的： 一种基于图的多点路径查询方法，该方法包括： 接收到查询请求时，获取该请求携带的起始顶点的集合V、扩展的层次数L和返回 的路径数量N； 针对V中的每个起始顶点扩展M层，将每个起始顶点对应的扩展信息分别记录到一 个数组中；并将扩展过程中经过的顶点和边使用邻接表进行缓存；其中，M小于L； 将V中的两两起始顶点对应的扩展信息求交集之后，再将所有交集内的扩展信息 求并集； 将并集中的扩展信息按照预设规则进行排列；并获取并集中前N条扩展信息作为 初步扩展信息； 根据缓存中的邻接表将初步扩展信息对应的每个顶点再扩展L-M层，并获取对应 的扩展信息作为二次扩展信息； 合并初步扩展信息和二次扩展信息，过滤掉非起始顶点对应的扩展信息，并按照 预设规则排列，作为待返回扩展信息； 获取待返回扩展信息中的前N条扩展信息，并将所述获取的前N条扩展信息中的路 4 CN 111611442 A 说　明　书 2/7 页 径信息响应给发送查询请求的设备。 一种基于图的多点路径查询装置，该装置包括：接收单元、获取单元、第一扩展单 元、第二扩展单元和响应单元； 所述接收单元，用于接收查询请求； 所述获取单元，用于当所述接收单元接收到查询请求时，获取该请求携带的起始 顶点的集合V、扩展的层次数L和返回的路径数量N； 所述第一扩展单元，用于针对获取单元中的V中的每个起始顶点扩展M层，将每个 起始顶点对应的扩展信息分别记录到一个数组中；并将扩展过程中经过的顶点和边使用邻 接表进行缓存；将V中的两两起始顶点对应的扩展信息求交集之后，再将所有交集内的扩展 信息求并集；将并集中的扩展信息按照预设规则进行排列；并获取并集中前N条扩展信息作 为初步扩展信息；其中，M小于L； 所述第二扩展单元，用于根据所述第一扩展单元在缓存中缓存的邻接表将初步扩 展信息对应的每个顶点再扩展L-M层，并获取对应的扩展信息作为二次扩展信息；合并初步 扩展信息和二次扩展信息，过滤掉非起始顶点对应的扩展信息，并按照预设规则排列，作为 待返回扩展信息；获取待返回扩展信息中的前N条扩展信息； 所述响应单元，用于将所述第二扩展单元获取的前N条扩展信息中的路径信息响 应给发送查询请求的设备。 一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计 算机程序，所述处理器执行所述程序时实现基于图的多点路径查询方法的步骤。 一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现 基于图的多点路径查询方法的步骤。 由上面的技术方案可知，本申请中通过先对起始顶点进行M层级的扩展，然后获取 扩展信息交集中的顶点进行剩余的L-M层级扩展，并按照返回路径数量反馈查询信息。针对 前M层级扩展后，进行扩展信息的交集处理，能够让数据信息得到收敛；再进行剩余的L-M层 级的扩展时，使用前M层级扩展产生的缓存数据，提升了查询效率。 附图说明 图1为本申请实施例中基于图的多点路径查询流程示意图； 图2为实施例中一图中顶点关系示意图； 图3为本申请实施例中应用于上述技术的装置结构示意图。