import java.util.*;/** * A test implementation of depth first search. * * @author Stefan Nilsson * @version 2007-02-13 */public class GraphAlgorithms{ private static final boolean DEBUG = false; public GraphAlgorithms() { } /** * Builds a graph g and prints the components of g to stdout. */ public void testSearch() { // The graph g: // // 0---1 2--- // | | | | // 3---4 ---- // | // 5 6---7 int size = 8; UndirectedGraph g = new MatrixGraph(size); g.addEdge(0, 1); g.addEdge(2, 2); g.addEdge(0, 3); g.addEdge(1, 4); g.addEdge(3, 4); g.addEdge(5, 3); g.addEdge(6, 7); System.out.println(); System.out.println(g); printComponentsDFS(g); } /** * Prints the components of g to stdout in depth-first order. * Each component is written on a separate line. */ public void printComponentsDFS(UndirectedGraph g) { int size = g.numVertices(); boolean[] visited = new boolean[size]; VertexAction action = new PrintAction(); System.out.println(); System.out.println("The components of g (DFS):"); // Do a DFS for each node that has not yet been visited. for (int v = 0; v < size; v++) { if (!visited[v]) { depthFirstSearch(g, v, visited, action); System.out.println(); } } } // @return [0] = componentCount, [1] = biggestElement public int[] DFS(UndirectedGraph g) { int[] data = new int[2]; int size = g.numVertices(); boolean[] visited = new boolean[size]; CountAction action = new CountAction(); for (int v = 0; v < size; v++) { if (!visited[v]) { depthFirstSearch(g, v, visited, action); data[0]++; } if(action.getBiggest(g) > data[1]) { data[1] = action.getBiggest(g); } action.reset(); } return data; } private static class PrintAction implements VertexAction { public void act(UndirectedGraph g, int v) { System.out.print(v + " "); } } private static class CountAction implements VertexAction { private int count; public void act(UndirectedGraph g, int v) { count++; } public int getBiggest(UndirectedGraph g) { return count; } public void reset() { count = 0; } } /** * Traverses the nodes of g that have not yet been visited. * The nodes are visited in depth-first order starting at a. * The act() method in the VertexAction object is called once for * each node. * * @param g an undirected graph. * @param a start vertex. * @param visited visited[i] is true iff node i has been visited. */ private void depthFirstSearch(UndirectedGraph g, int a, boolean[] visited, VertexAction action) { if (DEBUG) System.out.println("[=> DFS a=" + a + " " + visited[a] + "]"); if (visited[a]) return; visited[a] = true; action.act(g, a); VertexIterator vi = g.adjacentVertices(a); while (vi.hasNext()) depthFirstSearch(g, vi.next(), visited, action); if (DEBUG) System.out.println("[<= DFS a=" + a + "]"); } public void BFS(UndirectedGraph g, int start) { Queue Q = new ArrayDeque(g.numVertices()); Q.add(new Integer(start)); while (!Q.isEmpty()) { int v = ((Integer)Q.poll()).intValue(); for (Edge w = g.first(v); G.isEdge(w); w = G.next(w)) if (g.getMark(g.v2(w)) == 0) { g.setMark(G.v2(w), 1); Q.enqueue(new Integer(G.v2(w))); } PostVisit(G, v); } }}