1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
| 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 <tt>true</tt> if the graph is bipartite; <tt>false</tt> otherwise
*/
public boolean isBipartite() {
return isBipartite;
}
/**
* Returns the side of the bipartite that vertex <tt>v</tt> is on.
*
* @param v the vertex
* @return the side of the bipartition that vertex <tt>v</tt> is on; two vertices
* are in the same side of the bipartition if and only if they have the
* same color
* @throws IllegalArgumentException unless <tt>0 ≤ v < V</tt>
* @throws UnsupportedOperationException if this method is called when the graph
* is not bipartite
*/
public boolean color(int 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
* <tt>null</tt> otherwise.
*
* @return an odd-length cycle if the graph is not bipartite
* (and hence has an odd-length cycle), and <tt>null</tt>
* 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;
}
}
}
}
// graph has an odd-length cycle
else {
// 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;
}
/**
* Unit tests the <tt>Bipartite</tt> data type.
*/
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();
}
}
} |
(
