买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉广州大学申请的专利基于索引的最小生成树查询方法、系统、设备及介质获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN116701405B 。

龙图腾网通过国家知识产权局官网在2026-01-02发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202310811846.2，技术领域涉及：G06F16/22；该发明授权基于索引的最小生成树查询方法、系统、设备及介质是由欧阳典;黄卓;王卓然设计研发完成，并于2023-07-03向国家知识产权局提交的专利申请。

本基于索引的最小生成树查询方法、系统、设备及介质在说明书摘要公布了：本发明提供了一种有向图中基于索引的最小生成树查询方法、系统、设备及介质，涉及有向图技术领域，其中，方法包括：获取待查询网络的网络结构设置有向图的边及顶点从而获取有向图；将有向图中的环路收缩为单个顶点，并且记录当前的环路信息作为备选集索引，记录环路的最小连接出边作为连接集索引；在连接集索引上进行查询，并根据备选集索引得到最小边，查询最小生成树。本发明利用顶点收缩的特性，将最小边环路收缩成单个顶点，并生成备选集和连接集索引储存下来。通过索引将大量重复计算的部分作为备选集索引，记录环路之间的连接信息，直接在连接集上进行遍历，取代在图上进行搜索，大大减少查询时间。

本发明授权基于索引的最小生成树查询方法、系统、设备及介质在权利要求书中公布了：1.一种有向图中基于索引的最小生成树查询方法，其特征在于，包括： S1、获取待查询网络的网络结构设置有向图的边及顶点从而获取有向图； S2、将所述有向图中的环路收缩为单个顶点，并且记录当前的环路信息作为备选集索引，记录环路的最小连接出边作为连接集索引； S3、在连接集索引上进行查询，并根据备选集索引得到最小边，查询最小生成树； 所述S2具体包括： S21、遍历有向图中的所有顶点，计算出每个顶点的最小权值入边及其对应顶点； S22、针对S21中获取的每一个顶点u，递归寻找其入边顶点，如果返回到了顶点u，则得到了一个最小值环路，将所有的顶点遍历结束后，得到所有的最小值环路；并记录当前最小值环路信息，将环路中的点和边作为备选集索引储存起来；对于当前的最小值环路C，如果环路中的顶点存在收缩顶点C’，则将指向C’的最小边记录为连接边，并记录连接边的连接顶点，分别储存在连接集索引中C和C’对应出边索引和入边索引中； S23、将所有环路收缩为新顶点v’，并修改其他顶点到新顶点v’的边权值，用原来的权值减去该顶点最小值环路中的最小边权值，对整个有向图进行边收缩； S24、重复执行S21-S23直至有向图中没有环路，则备选集和连接集构建完成； 所述S3具体包括： S31、给定查询顶点V，找到其在连接集索引中所属的环路C； S32、在环路C中，以顶点V为根节点，根据备选集索引，删除根节点在环路中的入边，将环路C中剩余边加入最小生成树中； S33、如果环路C在连接集索引中有指向其他更小环路的连接边，则沿着连接出边去到更小的环路中，并以连接顶点为根节点，重复执行S32；如果该环路在连接集中有被其他更大环路指向的连接边，则沿着连接边去到更大的环路，并以环路C为根节点，重复S32；如果环路已经被搜索过，则跳过该环路； S34、如果所有被遍历到的环路，其指向的更小环路和被指向的更大环路都被搜索到了，则搜索结束，最小生成树查询结束。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人广州大学，其通讯地址为：510006 广东省广州市番禺区小谷围街道大学城外环西路230号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。