一种图算法友善的强连通图划分方法

摘要

本发明公开了一种图算法友善的强连通图划分方法，包括以下步骤：将图数据分解成若干个集合；利用多源宽度优先搜索算法将大小超过给定阈值的集合进一步划分成多个搜索树；利用启发式算法将搜索树组装成多个子图；本发明提供的强连通图划分方法可将强连通图划分成多个子图，而且与其他以割边即子图之间的边最小化、子图大小均衡为目标的现有hash或METIS划分方法均不同，在划分强连通图时考虑了边的方向和图数据的结构使得划分后的子图内部连通度较好、子图大小相对均衡，从而能有效提高图算法对其处理时的效率，解决在内存大小受限的限定条件下如何将大型强连通图划分成多个大小大致相同、连通度较好的子图的问题。