public class DFSDemo
1: //DFSDemo.java
3: import java.util.ArrayList;
4: import java.util.HashMap;
5: import java.util.HashSet;
6: import java.util.LinkedList;
7: import java.util.List;
8: import java.util.Queue;
9: import java.util.Scanner;
10: import java.util.Stack;
12: public class DFSDemo
13: {
14: public static void depthFirstSearch
15: (
16: Graph graph,
17: Vertex startVertex,
18: VertexVisitor visitor
19: )
20: {
21: Stack<Vertex> vertexStack = new Stack<Vertex>();
22: HashSet<Vertex> visitedSet = new HashSet<Vertex>();
24: vertexStack.push(startVertex);
26: while (vertexStack.size() > 0)
27: {
28: Vertex currentVertex = vertexStack.pop();
29: if (!visitedSet.contains(currentVertex))
30: {
31: visitor.visit(currentVertex);
32: visitedSet.add(currentVertex);
33: for (Edge edge : graph.getEdgesFrom(currentVertex))
34: {
35: Vertex adjacentVertex = edge.toVertex;
36: vertexStack.push(adjacentVertex);
37: }
38: }
39: }
40: }
42: public static void main(String[] args)
43: {
44: // Main program
45: // Creates 3 different graphs, each with vertices A through F,
46: // but with different sets of edges. Traverses each with DFS.
47: String[] vertexNames = { "A", "B", "C", "D", "E", "F" };
49: // Add the same set of vertices to 3 different graphs
50: Graph graph1 = new Graph();
51: Graph graph2 = new Graph();
52: Graph graph3 = new Graph();
53: Graph[] graphs = { graph1, graph2, graph3 };
54: for (String vertexName : vertexNames)
55: {
56: for (Graph graph : graphs)
57: {
58: graph.addVertex(vertexName);
59: }
60: }
62: // Add graph 1's edges
63: graph1.addUndirectedEdge(graph1.getVertex("A"), graph1.getVertex("B"));
64: graph1.addUndirectedEdge(graph1.getVertex("A"), graph1.getVertex("D"));
65: graph1.addUndirectedEdge(graph1.getVertex("B"), graph1.getVertex("E"));
66: graph1.addUndirectedEdge(graph1.getVertex("B"), graph1.getVertex("F"));
67: graph1.addUndirectedEdge(graph1.getVertex("C"), graph1.getVertex("F"));
68: graph1.addUndirectedEdge(graph1.getVertex("E"), graph1.getVertex("F"));
70: // Add graph 2's edges
71: graph2.addUndirectedEdge(graph2.getVertex("A"), graph2.getVertex("B"));
72: graph2.addUndirectedEdge(graph2.getVertex("B"), graph2.getVertex("C"));
73: graph2.addUndirectedEdge(graph2.getVertex("C"), graph2.getVertex("F"));
74: graph2.addUndirectedEdge(graph2.getVertex("D"), graph2.getVertex("E"));
75: graph2.addUndirectedEdge(graph2.getVertex("E"), graph2.getVertex("F"));
77: // Add graph 3's edges
78: graph3.addUndirectedEdge(graph3.getVertex("A"), graph3.getVertex("B"));
79: graph3.addUndirectedEdge(graph3.getVertex("A"), graph3.getVertex("E"));
80: graph3.addUndirectedEdge(graph3.getVertex("B"), graph3.getVertex("C"));
81: graph3.addUndirectedEdge(graph3.getVertex("B"), graph3.getVertex("E"));
82: graph3.addUndirectedEdge(graph3.getVertex("C"), graph3.getVertex("E"));
83: graph3.addUndirectedEdge(graph3.getVertex("D"), graph3.getVertex("E"));
84: graph3.addUndirectedEdge(graph3.getVertex("E"), graph3.getVertex("F"));
86: // Create the visitor that displays a vertex's label
87: VertexVisitor visitor = new PrintVisitor();
89: // Choose a starting vertex
90: String startVertexLabel = "A";
92: // Visit vertices in each graph with DFS
93: System.out.println("Depth-first search traversal");
94: for (int i = 0; i < graphs.length; i++)
95: {
96: System.out.printf("Graph %d: ", i + 1);
97: Vertex startVertex = graphs[i].getVertex(startVertexLabel);
98: depthFirstSearch(graphs[i], startVertex, visitor);
99: System.out.println();
100: }
101: }
102: }