All Routes From the Entrance to the Exit
Solve this ProblemYou are given a directed graph with no cycles, described as an adjacency list: graph[u] holds every node you can reach in one step from node u. Find every route from node 0 (the entrance) to node n-1 (the exit).
Because the graph has no cycles, a depth-first search cannot loop; recording the route while you walk and undoing each step on the way back (backtracking) lists all routes.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ n ≤ 8 nodes numbered 0 … n-1; the graph is directed and has no cycles - ◆
graph[u] lists, in increasing order, every node v that has a one-way road u → v (adjacency-list form of the graph) - ◆
The entrance is node 0 and the exit is node n-1 - ◆
Return every route from node 0 to node n-1 (each route is the list of nodes visited); the order of the routes does not matter
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Ordering of Nodes and Keep the Valid Ones
BruteEnumerate every sequence of distinct nodes that starts at 0 and ends at n-1 (choosing the nodes in between in every possible order). For each finished sequence, check that every consecutive pair is joined by a road, and keep it when all are. It ignores the graph while generating, so it wastes time on sequences that break at their first step: about n! sequences for n nodes.
O(n! · n)O(n)1class Solution {
2 private boolean hasEdge(int[] neighbours, int v) {
3 for (int x : neighbours) {
4 if (x == v) return true;
5 }
6 return false;
7 }
8
9 private void build(int[][] graph, List<Integer> path, boolean[] used, List<List<Integer>> answer) {
10 int n = graph.length;
11 int last = path.get(path.size() - 1);
12 if (last == n - 1) {
13 boolean valid = true;
14 for (int i = 0; i + 1 < path.size(); i++) {
15 if (!hasEdge(graph[path.get(i)], path.get(i + 1))) valid = false;
16 }
17 if (valid) answer.add(new ArrayList<>(path));
18 return;
19 }
20 for (int v = 0; v < n; v++) {
21 if (used[v]) continue;
22 used[v] = true;
23 path.add(v);
24 build(graph, path, used, answer);
25 path.remove(path.size() - 1);
26 used[v] = false;
27 }
28 }
29
30 public List<List<Integer>> allRoutes(int[][] graph) {
31 List<List<Integer>> answer = new ArrayList<>();
32 List<Integer> path = new ArrayList<>();
33 boolean[] used = new boolean[graph.length];
34 path.add(0);
35 used[0] = true;
36 build(graph, path, used, answer);
37 return answer;
38 }
39}Optimal — Depth-First Search With Backtracking
OptimalWalk the graph from node 0 following real roads only. Keep the current route in a list: push a node when you enter it, and pop it when you leave. When the walk reaches node n-1 record a copy of the route. Because the graph has no cycles, no node can repeat, so no visited array is needed. The work is proportional to the number of routes found (times their length), not to all possible orderings.
O(paths · n)O(n)1class Solution {
2 private void walk(int[][] graph, int node, List<Integer> path, List<List<Integer>> answer) {
3 path.add(node);
4 if (node == graph.length - 1) {
5 answer.add(new ArrayList<>(path));
6 } else {
7 for (int next : graph[node]) {
8 walk(graph, next, path, answer);
9 }
10 }
11 path.remove(path.size() - 1);
12 }
13
14 public List<List<Integer>> allRoutes(int[][] graph) {
15 List<List<Integer>> answer = new ArrayList<>();
16 walk(graph, 0, new ArrayList<>(), answer);
17 return answer;
18 }
19}