The example in this article describes how Java implements breadth-first traversal (BFS) to calculate the shortest path. Share it with everyone for your reference. The specific analysis is as follows:
We use strings to represent the vertex of the graph to simulate the Classroom, Square, Toilet, Canteen, South Gate, and North Gate locations in the school, and then calculate the shortest path between any two points.
As shown below:
For example, if I want to go from North Gate to Canteen, the output of the program should be:
BFS: From [North Gate] to [Canteen]:North GateSquareCanteen
First define an algorithm interface Algorithm:
public interface Algorithm { /** * Execute the algorithm*/ void perform(Graph g, String sourceVertex); /** * Get the path*/ Map<String, String> getPath();}Then, define the graph:
/** * (Undirected) graph*/public class Graph { // The starting point of the graph private String firstVertax; // Adjacency list private Map<String, List<String>> adj = new HashMap<>(); // Traversal Algorithm private Algorithm algorithm; public Graph(Algorithm algorithm) { this.algorithm = algorithm; } /** * Execute the algorithm*/ public void done() { algorithm.perform(this, firstVertax); } /** * Get the shortest path from the starting point to the {@code vertex} point * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack<>() ; stack.add(vertex); Map<String, String> path = algorithm.getPath(); for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax); return stack; } /** * Add an edge*/ public void addEdge(String fromVertex, String toVertex) { if (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); adj.get(toVertex).add(fromVertex); } /** * Add a vertex*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>()); } public Map<String, List<String>> getAdj() { return adj; }}Here we use the strategic design pattern to separate the algorithm from the Graph class, and select the traversal algorithm for the Graph by passing in an implementation of the Algorithm interface when constructing the Graph object.
public Graph(Algorithm algorithm) { this.algorithm = algorithm; }The storage structure of the undirected graph is an adjacency list. Here, a Map is used to represent the adjacency list. The key of the map is the school location (String), and the value is a location list (List<String>) connected to the location.
// Adjacency list private Map<String, List<String>> adj = new HashMap<>();
Then, write the BFS implementation of the Algorithm interface:
/** * Encapsulates the BFS algorithm*/public class BroadFristSearchAlgorithm implements Algorithm { // Save visited locations private List<String> visitedVertex; // Save the shortest path private Map<String, String> path; @Override public void perform( Graph g, String sourceVertex) { if (null == visitedVertex) { visitedVertex = new ArrayList<>(); } if (null == path) { path = new HashMap<>(); } BFS(g, sourceVertex); } @Override public Map<String, String> getPath() { return path; } private void BFS(Graph g, String sourceVertex) { Queue<String> queue = new LinkedList<>(); // Mark the starting point visitedVertex.add(sourceVertex); // Enqueue the starting point queue.add(sourceVertex); while (false == queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v : toBeVisitedVertex) { if (false == visitedVertex.contains( v)) { visitedVertex.add(v); path.put(v, ver); queue.add(v); } } } }}Among them, path is a Map type, which means a path from value to key.
BFS algorithm description:
1. Mark the origin as visited and put it in the queue.
2. Take a vertex from the queue and get all the vertices connected to the vertex.
3. Traverse these vertices, first determine whether the vertex has been visited, if not, mark the point as visited, record the current path, and enqueue the current vertex.
4. Repeat steps 2 and 3 until the queue is empty.
Test case:
String[] vertex = {"North Gate", "South Gate", "Classroom", "Square", "Toilet", "Canteen"}; Edge[] edges = { new Edge("North Gate", "Classroom" ), new Edge("North Gate", "Square"), new Edge("Classroom", "Toilet"), new Edge("Square", "Toilet"), new Edge("Square", "Canteen"), new Edge("Toilet", "South Gate"), new Edge("Toilet", "South Gate"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("Canteen"); System.out.println("BFS: From [North Gate] to [Canteen]:"); while (!result.isEmpty()) { System.out.println(result.pop()); } }I hope this article will be helpful to everyone’s Java programming.