二分图(二部图)
如何判断一个图是否是二分图,二分图就是可以将图分为两个部分,边都是在两个部分之间,而每个部分内部不可以有边相连。
这样如果二部图中存在一个环,那么这个环中的边数必须是偶数,可以画图验证一下三角形、四边形和五边形就知道了。
那么环中的边数是偶数,就可以利用染色算法来进行判别,环是偶数则两种颜色可以交替,否则必定有两个相邻的节点颜色相同。
可以利用BFS算法(结合队列)对二分图进行判别。关键代码如下:
输入:
7
1 4
1 5
1 6
2 5
3 5
3 6
3 4
2 6
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
//读入数据,并构建邻接表
int n = sc.nextInt();
int [] colors = new int[n];
HashMap <Integer, ArrayList<Integer>> hm = new HashMap<>();
for (int i = 0; i < n; i++) {
hm.put(i, new ArrayList<>());
}
while (sc.hasNext()) {
int forward = sc.nextInt();
int backward = sc.nextInt();
hm.get(forward).add(backward);
hm.get(backward).add(forward);
}
System.out.println(hm);
//这里节点的标识与数组的下表一一对应,也是为了简化问题,如果不是一一对应的情况,可能还需要做一次 index -> node 的转换
for (int i = 0; i < n; i++) {
int color = colors[i];
if (color == 0) {
boolean valid = BFS(hm, colors, i);
if (!valid) {
System.out.println("not valid");
System.out.println(Arrays.toString(colors));
return;
}
}
}
System.out.println("valid!");
System.out.println(Arrays.toString(colors));
}
public static boolean BFS(HashMap<Integer, ArrayList<Integer>> hm, int [] colors, int node) {
LinkedList<Integer> queue = new LinkedList<>();
colors[node] = 1;
queue.offerLast(node);
while(queue.size() != 0) {
int curNode = queue.pollFirst();
for (int neighber : hm.get(curNode)) {
if (colors[neighber] == 0) {
colors[neighber] = - colors[curNode];
queue.offerLast(neighber);
} else if (colors[neighber] == colors[curNode]){
return false;
}
}
}
return true;
}
二分图中一个很重要的问题就是最大匹配问题,最大匹配问题利用匈牙利算法进行求解。
输入:
8
1 1
1 2
2 2
2 3
3 1
3 2
4 3
4 4
关键代码如下:
static int maxn = 100;
//通过邻接矩阵进行图构建
static int [][] matrix = new int[maxn][maxn];
static boolean [] used = new boolean[maxn]; //表示某个轮次中女生是否被匹配过,每轮都初始化
static int [] nxt = new int[maxn]; //表示整个过程中与女生匹配的男生id ,nxt[1]=2, 表示女1和男2匹配
static int n = 5; //表示男生数量为4(数值多1是为了和输入的id从1开始相匹配)
static int m = 5; //表示女生数量为4
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
//构建邻接矩阵
int k = sc.nextInt();
for (int i = 0; i < k; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
matrix[a][b] = 1;
}
//开始遍历每个男生,尝试为每个男生匹配女生
int res = 0;
for (int i = 1; i <= n; i++) {
//每轮都要初始化女生是否匹配数组,因为dfs(递归)找增广路的时候需要标识来调整策略
used = new boolean[m];
if (DFS(i)) res ++;
}
System.out.println(res);
}
//这个方法是匈牙利算法的核心,函数标识在当前情况下,是否(返回值)能为男x成功匹配到女生。该函数还会修改每次初始化的used数组和nxt全局数组。
public static boolean DFS(int x) {
//遍历每个女生看看能不能和男生x匹配上
for (int i = 1; i <= m; i++) {
// 如果该女生和男生x存在可匹配的边,并且女生在这一轮没有匹配过
if (matrix[x][i] == 1 && !used[i]) {
//标识此轮中该女生被从尝试匹配过,防止递归找增广路的时候重复访问(增广路不是环,因此不能重复访问)
used[i] = true;
//如果这次循环没有找到,会对其他轮次的循环造成影响吗,因为你修改了used数组
//不会,因为如果存在一条增广路,经过了上次不成立的增广路,那么上次的也是一条增广路,产生矛盾。
//如果当前女生没有匹配的男生 || 当前女生有匹配的男生,并且可以让那个匹配的男生去找一个新的女生
if (nxt[i] == 0 || DFS(nxt[i])) {
nxt[i] = x;
return true;
}
}
}
return false;
}
单单看代码注释还是很难理解,可能过一阵子就忘了,结合代码单个步骤调试会更加形象,后面有空整一个视频讲解吧。
参考文献