分支限界法求最大割：无向图顶点集划分与优先队列算法

本资源是一份文档，涉及算法实验，具体是使用优先队列式分支限界法解决无向图的最大割问题。问题背景设定在一个具有n个部件的机器设计中，每个部件可以从m个供应商处购买，每个供应商提供的部件有不同的重量Wij和价格Cij。目标是找到一个总价格不超过给定上限d的最小重量机器设计，同时满足部件间的连接需求。 题目A是针对一个给定无向图G=(V,E)的问题，其中V是顶点集，E是边集。最大割任务是找到一个顶点集合U，使得U中的顶点与V-U之间的边最多。算法要求设计一个优先队列（如二叉堆）来辅助分支限界搜索，通过递归地剪枝搜索树来逐步逼近最大割。 输入部分首先定义了图的基本结构，包括顶点数n和边数m，以及边的连接情况。接下来是示例输入和输出格式，输入包括图的顶点和边的信息，输出则是最大割的边数和顶点集U的指示向量。 代码片段展示了如何定义一个Node类，用于表示搜索树中的节点，包括深度、割边数量、剩余边数量和解向量。Node类还定义了一个比较运算符，以便根据割边数量的大小决定优先级队列的排序。`addNode`函数用于将新节点添加到队列中，并更新解向量。 整体而言，该文档的核心知识点主要包括： 1. **无向图最大割问题**：理解和实现基于优先队列的分支限界算法，这是一种在图论中寻找最优解的经典方法。 2. **优先队列（如二叉堆）**：作为数据结构，用于存储和管理搜索过程中的节点，按照割边数量进行排序，保证总是选择当前割边最多的节点进行扩展。 3. **搜索策略**：递归地剪枝搜索树，确保每次选择增加割边数最多的扩展，直到达到某个解或超过成本限制。 4. **代码实现**：使用C++编写的具体实现，展示了如何创建节点、添加节点以及处理输入输出格式。 这个实验有助于学生掌握算法分析和优化技巧，以及在实际问题中应用搜索算法的能力。通过完成此类实验，学生可以深入理解并提高他们的编程技能，尤其是在处理图论问题时。