@Test public void testNoPathDFS(){ Graph<Integer> graph = createGraph(); List<Integer> path = graph.findPathDFS(10, 4); assertNull(path); }
@Override public List<V> findPathDFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Set<V> alreadyVisited = new HashSet<>(); Deque<V> stack = new ArrayDeque<>(); dfs(alreadyVisited, stack, start, end); if(isPathTo(stack, end)){ List<V> path = new ArrayList<>(stack); Collections.reverse(path); return path; } return null; }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathDFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Set<V> alreadyVisited = new HashSet<>(); Deque<V> stack = new ArrayDeque<>(); dfs(alreadyVisited, stack, start, end); if(isPathTo(stack, end)){ List<V> path = new ArrayList<>(stack); Collections.reverse(path); return path; } return null; } }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathDFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Set<V> alreadyVisited = new HashSet<>(); Deque<V> stack = new ArrayDeque<>(); dfs(alreadyVisited, stack, start, end); if(isPathTo(stack, end)){ List<V> path = new ArrayList<>(stack); Collections.reverse(path); return path; } return null; }  }
UndirectedGraph implements  Graph<V> { @Override public List<V> findPathDFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Set<V> alreadyVisited = new HashSet<>(); Deque<V> stack = new ArrayDeque<>(); dfs(alreadyVisited, stack, start, end); if(isPathTo(stack, end)){ List<V> path = new ArrayList<>(stack); Collections.reverse(path); return path; } return null; }  @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> findPathDFS(V start, V end) { if(! graph.containsKey(start) || ! graph.containsKey(end)){ return null; } if(start.equals(end)){ throw new IllegalArgumentException(); } Set<V> alreadyVisited = new HashSet<>(); Deque<V> stack = new ArrayDeque<>(); dfs(alreadyVisited, stack, start, end); if(isPathTo(stack, end)){ List<V> path = new ArrayList<>(stack); Collections.reverse(path); return path; } return null; }  @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);  }