一、定义
二分图（Bipartite Graph，又称为二部图），是图论中的一种特殊模型。
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集｛U｝、｛V｝，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集i∈ U，j∈ V，则称图G为一个二分图。
1-1 二分图示意图
二、基本思想
染色法：
二分图中所有顶点分属两个不同集合，U和V。所以，如果一个图是二分图，那对于任意顶点∈U，与它相邻的顶点肯定属于另一个集合V。
具体步骤如下：
- 从任意顶点出发（假设黑色），将其相邻顶点染成白色。
- 从该相邻顶点出发，将相邻顶点染成黑色（即与自身颜色相反）。
- 采用DFS进行上述过程的递归调用。
如果出现已访问过的相邻顶点颜色与自己相同，说明不是二分图。
三、源码实现
public class Bipartite {
private boolean isBipartite; // is the graph bipartite?
private boolean[] color; // color[v] gives vertices on one side of bipartition
private boolean[] marked; // marked[v] = true if v has been visited in DFS
private int[] edgeTo; // edgeTo[v] = last edge on path to v
private Stack<Integer> cycle; // odd-length cycle
/**
* Determines whether an undirected graph is bipartite and finds either a
* bipartition or an odd-length cycle.
*
* @param G the graph
*/
public Bipartite(Graph G) {
isBipartite = true;
color = new boolean[G.V()];
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
dfs(G, v);
}
}
assert check(G);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
// short circuit if odd-length cycle found
if (cycle != null) return;
// found uncolored vertex, so recur
if (!marked[w]) {
edgeTo[w] = v;
color[w] = !color[v];
dfs(G, w);
}
// if v-w create an odd-length cycle, find it
else if (color[w] == color[v]) {
isBipartite = false;
cycle = new Stack<Integer>();
cycle.push(w); // don't need this unless you want to include start vertex twice
for (int x = v; x != w; x = edgeTo[x]) {
cycle.push(x);
}
cycle.push(w);
}
}
}
/**
* Returns true if the graph is bipartite.
*
* @return {@code true} if the graph is bipartite; {@code false} otherwise
*/
public boolean isBipartite() {
return isBipartite;
}
/**
* Returns the side of the bipartite that vertex {@code v} is on.
*
* @param v the vertex
* @return the side of the bipartition that vertex {@code v} is on; two vertices
* are in the same side of the bipartition if and only if they have the
* same color
* @throws IllegalArgumentException unless {@code 0 <= v < V}
* @throws UnsupportedOperationException if this method is called when the graph
* is not bipartite
*/
public boolean color(int v) {
validateVertex(v);
if (!isBipartite)
throw new UnsupportedOperationException("graph is not bipartite");
return color[v];
}
/**
* Returns an odd-length cycle if the graph is not bipartite, and
* {@code null} otherwise.
*
* @return an odd-length cycle if the graph is not bipartite
* (and hence has an odd-length cycle), and {@code null}
* otherwise
*/
public Iterable<Integer> oddCycle() {
return cycle;
}
private boolean check(Graph G) {
// graph is bipartite
if (isBipartite) {
for (int v = 0; v < G.V(); v++) {
for (int w : G.adj(v)) {
if (color[v] == color[w]) {
System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
return false;
}
}
}
}else { // graph has an odd-length cycle
// verify cycle
int first = -1, last = -1;
for (int v : oddCycle()) {
if (first == -1) first = v;
last = v;
}
if (first != last) {
System.err.printf("cycle begins with %d and ends with %d\n", first, last);
return false;
}
}
return true;
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
int V = marked.length;
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
/**
* Unit tests the {@code Bipartite} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
int V1 = Integer.parseInt(args[0]);
int V2 = Integer.parseInt(args[1]);
int E = Integer.parseInt(args[2]);
int F = Integer.parseInt(args[3]);
// create random bipartite graph with V1 vertices on left side,
// V2 vertices on right side, and E edges; then add F random edges
Graph G = GraphGenerator.bipartite(V1, V2, E);
for (int i = 0; i < F; i++) {
int v = StdRandom.uniform(V1 + V2);
int w = StdRandom.uniform(V1 + V2);
G.addEdge(v, w);
}
StdOut.println(G);
Bipartite b = new Bipartite(G);
if (b.isBipartite()) {
StdOut.println("Graph is bipartite");
for (int v = 0; v < G.V(); v++) {
StdOut.println(v + ": " + b.color(v));
}
}else {
StdOut.print("Graph has an odd-length cycle: ");
for (int x : b.oddCycle()) {
StdOut.print(x + " ");
}
StdOut.println();
}
}
}
