一种基于网络流的平衡分割方法

本发明涉及一种基于网络流的平衡分割方法，属于电子设计自动化领域，该方法包括以下步骤：建立网络流图，选择网络流图中的其中一个节点为源点，另一个节点为汇点；设置网络流图的初始最大流为0；搜索从源点到汇点的未被搜索过的路径；以该路径上的最小边权的边的权重作为该路径的最小流，更新网络流图的最大流和该路径经过的每一条边的权重；形成切割边界；判断分割后两组节点的权重和是否平衡，若平衡，输出分割结果，若不平衡，遍历权重较大的组的节点并将遍历到的节点加到源点或汇点中，找到切割代价最小的情况作为新的切割方案，直至分割后两组节点的权重达到平衡。该方法切割代价更小，能够处理有方向的信号，提升了基于网络流的分割速度。