@Test public void randomTest() { int N = 2000; for (int i = 10; i <= N; i *= 2) { List<Integer>[] graph = GraphBuilder.buildRandomUndirectGraph(i, true); Assert.assertEquals(expect(graph), NonrecursiveDFS.dfs(graph)); } }
public static List<Integer> dfs(List<Integer>[] graph) { Deque<Integer> st = new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); boolean[] seen = new boolean[graph.length]; st.push(0); while (!st.isEmpty()) { int cur = st.pop(); if (seen[cur]) continue; seen[cur] = true; res.add(cur); List<Integer> nei = graph[cur]; for (int i = nei.size() - 1; i >= 0; i--) { st.push(nei.get(i)); } } return res; }
NonrecursiveDFS { public static List<Integer> dfs(List<Integer>[] graph) { Deque<Integer> st = new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); boolean[] seen = new boolean[graph.length]; st.push(0); while (!st.isEmpty()) { int cur = st.pop(); if (seen[cur]) continue; seen[cur] = true; res.add(cur); List<Integer> nei = graph[cur]; for (int i = nei.size() - 1; i >= 0; i--) { st.push(nei.get(i)); } } return res; } }
NonrecursiveDFS { public static List<Integer> dfs(List<Integer>[] graph) { Deque<Integer> st = new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); boolean[] seen = new boolean[graph.length]; st.push(0); while (!st.isEmpty()) { int cur = st.pop(); if (seen[cur]) continue; seen[cur] = true; res.add(cur); List<Integer> nei = graph[cur]; for (int i = nei.size() - 1; i >= 0; i--) { st.push(nei.get(i)); } } return res; }  }
NonrecursiveDFS { public static List<Integer> dfs(List<Integer>[] graph) { Deque<Integer> st = new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); boolean[] seen = new boolean[graph.length]; st.push(0); while (!st.isEmpty()) { int cur = st.pop(); if (seen[cur]) continue; seen[cur] = true; res.add(cur); List<Integer> nei = graph[cur]; for (int i = nei.size() - 1; i >= 0; i--) { st.push(nei.get(i)); } } return res; }  static List<Integer> dfs(List<Integer>[] graph); }
NonrecursiveDFS { public static List<Integer> dfs(List<Integer>[] graph) { Deque<Integer> st = new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); boolean[] seen = new boolean[graph.length]; st.push(0); while (!st.isEmpty()) { int cur = st.pop(); if (seen[cur]) continue; seen[cur] = true; res.add(cur); List<Integer> nei = graph[cur]; for (int i = nei.size() - 1; i >= 0; i--) { st.push(nei.get(i)); } } return res; }  static List<Integer> dfs(List<Integer>[] graph);  }