听起来您正在寻找图表的最小切割。有很多关于这个主题的文献。您可以重复应用最小切割，直到您拥有连接良好的组件的层次结构。

我遇到过非常相似的情况，虽然在不同的领域。在处理稀疏矩阵时，很少有元素仅存在于对角线/对角线周围的带中的情况。仅通过存储对角线信息就可以非常有效地存储它们，并且可以设计非常有效的算法。但是，在某些情况下，稀疏矩阵可能不是对角线形式。但是，我们可以对邻接矩阵应用一些变换（如果位置具有非零条目，则矩阵具有条目 1，否则为 0）。这是一个正方形、对称、非零、可能密集的矩阵，我们希望将其转换为块对角线形式，这正是您想要做的。我所知道的完成这项工作的标准算法称为 Cuthill Mckee 算法。该算法直观地遵循广度优先搜索算法。第一个元素的选择至关重要，算法的结果是基于邻居排序的启发式算法。在典型情况下，Reversed Cuthill Mckee 算法的结果稍好一些。我希望这会有所帮助。