public class BFSDemo
1: //BFSDemo.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;
11: public class BFSDemo
12: {
13: public static List<Vertex> breadthFirstSearch
14: (
15: Graph graph,
16: Vertex startVertex
17: )
18: {
19: return breadthFirstSearch
20: (
21: graph, startVertex,
22: new HashMap<Vertex, Double>()
23: );
24: }
26: public static List<Vertex> breadthFirstSearch
27: (
28: Graph graph,
29: Vertex startVertex,
30: HashMap<Vertex, Double> distances
31: )
32: {
33: HashSet<Vertex> discoveredSet = new HashSet<Vertex>();
34: Queue<Vertex> frontierQueue = new LinkedList<Vertex>();
35: ArrayList<Vertex> visitedList = new ArrayList<Vertex>();
37: // startVertex has a distance of 0 from itself
38: distances.put(startVertex, 0.0);
40: frontierQueue.add(startVertex); // Enqueue startVertex in frontierQueue
41: discoveredSet.add(startVertex); // Add startVertex to discoveredSet
43: while (frontierQueue.size() > 0)
44: {
45: Vertex currentVertex = frontierQueue.remove();
46: visitedList.add(currentVertex);
47: for (Edge edge : graph.getEdgesFrom(currentVertex))
48: {
49: Vertex adjacentVertex = edge.toVertex;
50: if (!discoveredSet.contains(adjacentVertex))
51: {
52: frontierQueue.add(adjacentVertex);
53: discoveredSet.add(adjacentVertex);
55: // Distance of adjacentVertex is 1 more than currentVertex
56: distances.put
57: (
58: adjacentVertex,
59: distances.get(currentVertex) + 1
60: );
61: }
62: }
63: }
64: return visitedList;
65: }
67: public static void main(String[] args)
68: {
69: Graph peopleGraph = new Graph();
70: Vertex vertexA = peopleGraph.addVertex("Joe");
71: Vertex vertexB = peopleGraph.addVertex("Eva");
72: Vertex vertexC = peopleGraph.addVertex("Taj");
73: Vertex vertexD = peopleGraph.addVertex("Chen");
74: Vertex vertexE = peopleGraph.addVertex("Lily");
75: Vertex vertexF = peopleGraph.addVertex("Jun");
76: Vertex vertexG = peopleGraph.addVertex("Ken");
78: // Add graph edges
79: peopleGraph.addUndirectedEdge(vertexA, vertexB); // From Joe to Eva
80: peopleGraph.addUndirectedEdge(vertexA, vertexC); // From Joe to Taj
81: peopleGraph.addUndirectedEdge(vertexB, vertexE); // From Eva to Lily
82: peopleGraph.addUndirectedEdge(vertexC, vertexD); // From Taj to Chen
83: peopleGraph.addUndirectedEdge(vertexC, vertexE); // From Taj to Lily
84: peopleGraph.addUndirectedEdge(vertexD, vertexF); // From Chen to Jun
85: peopleGraph.addUndirectedEdge(vertexE, vertexF); // From Lily to Jun
86: peopleGraph.addUndirectedEdge(vertexF, vertexG); // From Jun to Ken
88: // Ask the user for the starting person's name
89: Scanner scnr = new Scanner(System.in);
90: System.out.print("Enter the starting person's name: ");
91: String startName = scnr.nextLine();
92: System.out.println();
94: // Search for the start vertex
95: Vertex startVertex = null;
96: for (Vertex vertex : peopleGraph.getVertices())
97: {
98: if (startName.equals(vertex.label))
99: {
100: startVertex = vertex;
101: }
102: }
104: if (startVertex == null)
105: {
106: System.out.printf("Start vertex \"%s\" not found%n", startName);
107: }
108: else
109: {
110: HashMap<Vertex, Double> vertexDistances =
111: new HashMap<Vertex, Double>();
112: List<Vertex> visitedList =
113: breadthFirstSearch(peopleGraph, startVertex, vertexDistances);
115: // Output the result
116: System.out.println("Breadth-first search traversal");
117: System.out.printf("Start vertex: %s%n", startVertex.label);
118: for (Vertex vertex : visitedList)
119: {
120: System.out.println(vertex.label + ": " + vertexDistances.get(
121: vertex).intValue());
122: }
123: }
124: }
125: }