Test degrees of connectedness
TwoExists.java-- check whether there is a cycle in the graph.
public static class GraphVertex {
public enum Color {
WHITE, GRAY, BLACK
}
public Color color;
public List<GraphVertex> edges;
public GraphVertex() {
color = Color.WHITE;
edges = new ArrayList<>();
}
public String toString() {
return edges.toString();
}
}
public static boolean isGraphTwoExist(List<GraphVertex> G) {
if (!G.isEmpty()) {
return DFS(G.get(0), null);
}
return false;
}
private static boolean DFS(GraphVertex cur, GraphVertex pre) {
// Visiting a gray vertex means a cycle.
if (cur.color == GraphVertex.Color.GRAY) {
return true;
}
cur.color = GraphVertex.Color.GRAY; // marks current vertex as a gray one.
// Traverse the neighbor vertices.
for (GraphVertex next : cur.edges) {
if (next != pre && next.color != GraphVertex.Color.BLACK) {
if (DFS(next, cur)) {
return true;
}
}
}
cur.color = GraphVertex.Color.BLACK; // marks current vertex as black.
return false;
}
TwoForAll.java
public static class GraphVertex {
public int d, l; // discovery and leaving time.
public List<GraphVertex> edges;
public GraphVertex() {
d = 0;
l = Integer.MAX_VALUE;
edges = new ArrayList<>();
}
public String toString() {
return edges.toString();
}
}
public static boolean isGraphTwoForAll(List<GraphVertex> G) {
if (!G.isEmpty()) {
return DFS(G.get(0), null, 0);
}
return true;
}
private static boolean DFS(GraphVertex cur, GraphVertex pre, int time) {
cur.d = ++time;
cur.l = Integer.MAX_VALUE;
for (GraphVertex next : cur.edges) {
if (next != pre) {
if (next.d != 0) { // back edge.
cur.l = Math.min(cur.l, next.d);
} else { // forward edge.
if (!DFS(next, cur, time)) {
return false;
}
cur.l = Math.min(cur.l, next.l);
}
}
}
return (pre == null || cur.l < cur.d);
}
