@Test public void testDfsSingleNode() { final graph.model.MutableDirectedGraph<String> g = new MutableDirectedGraph<>(); g.addNode("a"); final List<String> dfs = Dfs.traverseDepthFirst(g, "a"); assertEquals(Arrays.asList("a"), dfs); }
public static <N> List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode) { Preconditions.checkArgument(graph.nodes().contains(startingNode)); final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final List<N> result = new ArrayList<>(n); final Set<N> closed = new HashSet<>(n); final Stack<N> open = new Stack<>(); open.push(startingNode); while (!open.isEmpty()) { final N active = open.pop(); if (!closed.contains(active)) { result.add(active); closed.add(active); open.addAll(graph.successors(active)); } } return result; }
Dfs { public static <N> List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode) { Preconditions.checkArgument(graph.nodes().contains(startingNode)); final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final List<N> result = new ArrayList<>(n); final Set<N> closed = new HashSet<>(n); final Stack<N> open = new Stack<>(); open.push(startingNode); while (!open.isEmpty()) { final N active = open.pop(); if (!closed.contains(active)) { result.add(active); closed.add(active); open.addAll(graph.successors(active)); } } return result; } }
Dfs { public static <N> List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode) { Preconditions.checkArgument(graph.nodes().contains(startingNode)); final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final List<N> result = new ArrayList<>(n); final Set<N> closed = new HashSet<>(n); final Stack<N> open = new Stack<>(); open.push(startingNode); while (!open.isEmpty()) { final N active = open.pop(); if (!closed.contains(active)) { result.add(active); closed.add(active); open.addAll(graph.successors(active)); } } return result; }  }
Dfs { public static <N> List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode) { Preconditions.checkArgument(graph.nodes().contains(startingNode)); final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final List<N> result = new ArrayList<>(n); final Set<N> closed = new HashSet<>(n); final Stack<N> open = new Stack<>(); open.push(startingNode); while (!open.isEmpty()) { final N active = open.pop(); if (!closed.contains(active)) { result.add(active); closed.add(active); open.addAll(graph.successors(active)); } } return result; }  static List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode); }
Dfs { public static <N> List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode) { Preconditions.checkArgument(graph.nodes().contains(startingNode)); final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final List<N> result = new ArrayList<>(n); final Set<N> closed = new HashSet<>(n); final Stack<N> open = new Stack<>(); open.push(startingNode); while (!open.isEmpty()) { final N active = open.pop(); if (!closed.contains(active)) { result.add(active); closed.add(active); open.addAll(graph.successors(active)); } } return result; }  static List<N> traverseDepthFirst(final Graph<N, ?> graph, final N startingNode);  }