无向图的最大割问题（分支限界）哈哈哈哈哈哈哈哈的博客-

一、需求分析

0.问题描述

给定一个无向图G=(V, E),设是G的顶点集。对任意(u, v)∈E,若u∈U，且v∈V-U,就称(u, 1)为关于顶点集U的一条割边。顶点集U的所有割边构成图G的一个割。G的最大割是指G中所含边数最多的割。

对于给定的无向图G,设计一个优先队列式分支限界法，计算G的最大割。

1.问题分析

①解向量：（x1,x2,……xn)是一个01序列，其中xi=1表示点xi在割集，0表示不在割集

②解空间：完全二叉树，子集树

③约束条件：只有考察右子结点的时候，需要判断是否剪枝。假设当前的割边数加上剩余的边数都没有最优解大，那么就剪去。

④优先级：每个结点的当前割边数

2.输入数据

输入集合的点数n和边数e，然后输入e条边的起始点和终止点

3.输出数据

输出最大割的值和相应的解向量

二、算法设计与分析

1.算法的基本思想

解空间树是棵完全二叉树，第i层表示对第i个点的处理，从根结点开始处理，每个结点保存自己所在的层数，当前的割边数量，剩余的割边数量和当前的部分解。

• 用优先队列存储每个待访问的结点，优先级设置为割边的数量。
• 不断从队列里面取出队首的结点进行处理。
• 扩展结点的左子结点一定可以加入，并计算其当前的割边树和剩余边数，记录它的当前解。
• 考察扩展结点的右子结点时，当当前割边数+剩余边数>当前最优解时，加入队列。
• 如果到达叶子节点，必定就是最优解。

2.输入和输出的格式

从文件输入，输出到文件。

3.算法的具体步骤

4.算法的时空分析

①时间复杂度：最坏情况下要遍历整棵树，O（2^n)

②空间复杂度：最坏情况下要保存最后一层的所有结点，每个结点要记录当前的解，O（n*2^n)

三、测试结果

 测试数据： 7 18 1 4 1 5 1 6 1 7 2 3 2 4 2 5 2 6 2 7 3 4 3 5 3 6 3 7 4 5 4 6 5 6 5 7 6 7  结果： 12 1 1 1 0 1 0 0

 #include <bits/stdc++.h> #include <fstream> #include <iostream>  using namespace std;  const int MAX = 1000; int G[MAX][MAX];//存储边信息  int bestx[MAX];//最优值的割集  int w[MAX];//顶点的权 int n, e; //顶点数，边数  ifstream in("input.txt"); ofstream out("output.txt");   //结点类  class Node { public:     int dep;  //当前层     int cut;  //割边数量     int e;    //剩余边的数量     int *x;   //解向量      Node(int d, int c, int ee)     {         x = new int[n+1];         dep = d;         cut = c;         e = ee;     }      //割边数大的先出队列     bool operator < (const Node &node) const     {         return cut < node.cut;     } };  //存储待解决的结点的优先队列  priority_queue<Node> q;  //添加结点 void addNode(Node enode, bool isLeft) {     Node now(enode.dep+1, enode.cut, enode.e);     copy(enode.x, enode.x+n+1, now.x);     //是左结点      if(isLeft)     {         now.x[now.dep] = 1;//标记是割集元素          for(int j=1; j<=n; j++)//统计割边的增量              if(G[now.dep][j])                 if(now.x[j] == 0) //如果当前顶点在割集中，但边的另一个顶点不在割集                 {                     now.cut++;  //割边的数量增加                     now.e--;    //剩余边的数量减少                 }                 else                     now.cut--;//否则割边数量减少      }     else//右节点      {          now.x[now.dep] = 0;//标记不是割集元素          now.e--;//剩余边的数量减少     }     q.push(now);//加入优先队列  }  int search() {  //初始化      Node enode(0, 0, e);     for(int j=1; j<=n; j++)         enode.x[j] = 0;     int best = 0;     //分支限界求解      while(true)     {         if(enode.dep>n)//到达叶子节点，如果比当前最优解更优，更新          {             if(enode.cut > best)             {                 best = enode.cut;                 copy(enode.x, enode.x+n+1, bestx);                 break;             }         }         else//没有到达叶子节点          {             addNode(enode, true);//加入左子结点              if(enode.cut + enode.e > best)//满足约束条件，加入右子结点                  addNode(enode, false);         }         if(q.empty())             break;         else//取出队首元素          {             enode = q.top();             q.pop();          }     }     return best; }  int main() {  int a, b, i;     in>>n>>e;         memset(G, 0, sizeof(G));     for(i=1; i<=e; i++)     {         in >> a >> b;         G[a][b] = G[b][a] = 1;     }     out << search()<<'n';     for(i=1; i<=n; i++){      out << bestx[i];      if(i!=n) out<<" ";  }     out<<'n';        in.close();     out.close();     return 0; } 

代码借鉴博主：じ☆ve角落里暗殇灬的博客