@Test public void testShortestPath_simple() { Graph<Integer> graph = createGraph(); List<Integer> path = graph.findPathBFS(1, 2); assertNotNull(path); assertEquals(2, path.size()); assertEquals(1, (int) path.get(0)); assertEquals(2, (int) path.get(1)); }
@Override public List<V> findPathBFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Queue<V> queue = new ArrayDeque<>(); Map<V,V> bestParent = new HashMap<>(); queue.add(start); mainLoop: while(! queue.isEmpty()){ V parent = queue.poll(); for(V child : graph.get(parent)){ if( child.equals(start) || bestParent.get(child) != null){ continue; } bestParent.put(child, parent); if(child.equals(end)){ break mainLoop; } queue.add(child); } } if(! bestParent.containsKey(end)){ return null; } List<V> path = new ArrayList<>(); V current = end; while (current != null){ path.add(0, current); current = bestParent.get(current); } return path; }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathBFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Queue<V> queue = new ArrayDeque<>(); Map<V,V> bestParent = new HashMap<>(); queue.add(start); mainLoop: while(! queue.isEmpty()){ V parent = queue.poll(); for(V child : graph.get(parent)){ if( child.equals(start) || bestParent.get(child) != null){ continue; } bestParent.put(child, parent); if(child.equals(end)){ break mainLoop; } queue.add(child); } } if(! bestParent.containsKey(end)){ return null; } List<V> path = new ArrayList<>(); V current = end; while (current != null){ path.add(0, current); current = bestParent.get(current); } return path; } }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathBFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Queue<V> queue = new ArrayDeque<>(); Map<V,V> bestParent = new HashMap<>(); queue.add(start); mainLoop: while(! queue.isEmpty()){ V parent = queue.poll(); for(V child : graph.get(parent)){ if( child.equals(start) || bestParent.get(child) != null){ continue; } bestParent.put(child, parent); if(child.equals(end)){ break mainLoop; } queue.add(child); } } if(! bestParent.containsKey(end)){ return null; } List<V> path = new ArrayList<>(); V current = end; while (current != null){ path.add(0, current); current = bestParent.get(current); } return path; }  }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathBFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Queue<V> queue = new ArrayDeque<>(); Map<V,V> bestParent = new HashMap<>(); queue.add(start); mainLoop: while(! queue.isEmpty()){ V parent = queue.poll(); for(V child : graph.get(parent)){ if( child.equals(start) || bestParent.get(child) != null){ continue; } bestParent.put(child, parent); if(child.equals(end)){ break mainLoop; } queue.add(child); } } if(! bestParent.containsKey(end)){ return null; } List<V> path = new ArrayList<>(); V current = end; while (current != null){ path.add(0, current); current = bestParent.get(current); } return path; }  @Override void addVertex(V vertex); @Override void addEdge(V from, V to); @Override int getNumberOfVertices(); @Override int getNumberOfEdges(); @Override void removeEdge(V from, V to); @Override void removeVertex(V vertex); @Override Collection<V> getAdjacents(V vertex); @Override List<V> findPathDFS(V start, V end); @Override List<V> findPathBFS(V start, V end); @Override Set<V> findConnected(V vertex); @Override Set<V> findConnected(Iterable<V> vertices); }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathBFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Queue<V> queue = new ArrayDeque<>(); Map<V,V> bestParent = new HashMap<>(); queue.add(start); mainLoop: while(! queue.isEmpty()){ V parent = queue.poll(); for(V child : graph.get(parent)){ if( child.equals(start) || bestParent.get(child) != null){ continue; } bestParent.put(child, parent); if(child.equals(end)){ break mainLoop; } queue.add(child); } } if(! bestParent.containsKey(end)){ return null; } List<V> path = new ArrayList<>(); V current = end; while (current != null){ path.add(0, current); current = bestParent.get(current); } return path; }  @Override void addVertex(V vertex); @Override void addEdge(V from, V to); @Override int getNumberOfVertices(); @Override int getNumberOfEdges(); @Override void removeEdge(V from, V to); @Override void removeVertex(V vertex); @Override Collection<V> getAdjacents(V vertex); @Override List<V> findPathDFS(V start, V end); @Override List<V> findPathBFS(V start, V end); @Override Set<V> findConnected(V vertex); @Override Set<V> findConnected(Iterable<V> vertices);  }