▶ 书中第四章部分程序，包括在加上自己补充的代码，二分图的判定和染色
● 二分图 1
//+-----------------------------------------------------------------------------
// 第四章，二分图
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.GraphGenerator;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Stack; public class class01
{
private boolean isBipartite;
private boolean[] color; // 顶点染色情况
private boolean[] marked;
private int[] edgeTo;
private Stack<Integer> cycle; // odd-length cycle public class01(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);
}
}
} private void dfs(Graph G, int v)
{
marked[v] = true;
for (int w : G.adj(v))
{
if (cycle != null) // 已经有奇数环，停止递归
return;
if (!marked[w]) // 正常的标记、染色、继续递归
{
edgeTo[w] = v;
color[w] = !color[v];
dfs(G, w);
}
else if (color[w] == color[v]) // v ~ w 形成了长度为奇数的环
{
isBipartite = false;
cycle = new Stack<Integer>();
for (int x = v; x != w; x = edgeTo[x]) // 把从 v 到 w 的顶点压栈，保存有问题的环部分
cycle.push(x);
cycle.push(w);
}
}
} public boolean isBipartite()
{
return isBipartite;
} public boolean color(int v)
{
if (!isBipartite)
throw new UnsupportedOperationException("\n<color> Graph is not bipartite.\n");
return color[v];
} public Iterable<Integer> oddCycle()
{
return cycle;
} public static void main(String[] args)
{
int V1 = Integer.parseInt(args[0]); // 生成 G(V1 + V2, E) 顶点的二分图，再随机添加 F 条边
int V2 = Integer.parseInt(args[1]);
int E = Integer.parseInt(args[2]);
int F = Integer.parseInt(args[3]); 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); class01 b = new class01(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();
}
}
}
● 二分图 2
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.GraphGenerator;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.Queue; public class class01
{
private boolean isBipartite; // 是否为二分图
private boolean[] color; // 顶点染色
private boolean[] marked;
private int[] edgeTo;
private Queue<Integer> cycle; // 存储了奇数长度的环（二分图则队列为空） public class01(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() && isBipartite; v++)
{
if (!marked[v])
bfs(G, v); // 广度优先遍历
}
} private void bfs(Graph G, int s)
{
Queue<Integer> q = new Queue<Integer>();
color[s] = false; // 颜色使用 true / false
marked[s] = true;
for (q.enqueue(s); !q.isEmpty();)
{
int v = q.dequeue();
for (int w : G.adj(v))
if (!marked[w])
{
marked[w] = true;
edgeTo[w] = v;
color[w] = !color[v];
q.enqueue(w);
}
else if (color[w] == color[v]) // w 已经遍历过，且形成了奇数长度的环
{
isBipartite = false;
cycle = new Queue<Integer>();
Stack<Integer> stack = new Stack<Integer>();
int x = v, y = w; // 两端同时向回走，color[v] == color[w] 于是 color[x] == color[y]
for (; x != y; x = edgeTo[x], y = edgeTo[y]) // 存在节点 z 使得 edgeTo[x] == edgeTo[y] == z，循环结束时 x 和 y 均指向公共顶点 z
{
stack.push(x);
cycle.enqueue(y);
}
for (stack.push(x); !stack.isEmpty(); cycle.enqueue(stack.pop())); // 公共顶点 z 压栈，然后吐栈拼入队列，多一步是防止本来栈空
cycle.enqueue(w);
return;
}
}
} public boolean isBipartite()
{
return isBipartite;
} public boolean color(int v)
{
if (!isBipartite)
throw new UnsupportedOperationException("\n<color> Graph is not bipartite.\n");
return color[v];
} public Iterable<Integer> oddCycle()
{
return cycle;
} 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]);
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); class01 b = new class01(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();
}
}
}