|
| 1 | +##1. Depth First Search |
| 2 | + |
| 3 | +::tabs-start |
| 4 | + |
| 5 | +```python |
| 6 | +classSolution: |
| 7 | + |
| 8 | +# We don't use the state WHITE as such anywhere. Instead, the "null" value in the states array below is a substitute for WHITE. |
| 9 | +GRAY=1 |
| 10 | +BLACK=2 |
| 11 | + |
| 12 | +defleadsToDestination(self,n:int,edges: List[List[int]],source:int,destination:int) ->bool: |
| 13 | + graph=self.buildDigraph(n, edges) |
| 14 | +returnself.leadsToDest(graph, source, destination, [None]* n) |
| 15 | + |
| 16 | +defleadsToDest(self,graph,node,dest,states): |
| 17 | + |
| 18 | +# If the state is GRAY, this is a backward edge and hence, it creates a Loop. |
| 19 | +if states[node]!=None: |
| 20 | +return states[node]== Solution.BLACK |
| 21 | + |
| 22 | +# If this is a leaf node, it should be equal to the destination. |
| 23 | +iflen(graph[node])==0: |
| 24 | +return node== dest |
| 25 | + |
| 26 | +# Now, we are processing this node. So we mark it as GRAY. |
| 27 | + states[node]= Solution.GRAY |
| 28 | + |
| 29 | +for next_nodein graph[node]: |
| 30 | + |
| 31 | +# If we get a `false` from any recursive call on the neighbors, we short circuit and return from there. |
| 32 | +ifnotself.leadsToDest(graph, next_node, dest, states): |
| 33 | +returnFalse |
| 34 | + |
| 35 | +# Recursive processing done for the node. We mark it BLACK. |
| 36 | + states[node]= Solution.BLACK |
| 37 | +returnTrue |
| 38 | + |
| 39 | +defbuildDigraph(self,n,edges): |
| 40 | + graph= [[]for _inrange(n)] |
| 41 | + |
| 42 | +for edgein edges: |
| 43 | + graph[edge[0]].append(edge[1]) |
| 44 | + |
| 45 | +return graph |
| 46 | +``` |
| 47 | + |
| 48 | +```java |
| 49 | +classSolution { |
| 50 | + |
| 51 | +// We don't use the state WHITE as such anywhere. Instead, the "null" value in the states array below is a substitute for WHITE. |
| 52 | +enumColor {GRAY,BLACK }; |
| 53 | + |
| 54 | +publicbooleanleadsToDestination(intn,int[][]edges,intsource,intdestination) { |
| 55 | + |
| 56 | +List<Integer>[] graph= buildDigraph(n, edges); |
| 57 | +return leadsToDest(graph, source, destination,newColor[n]); |
| 58 | + } |
| 59 | + |
| 60 | +privatebooleanleadsToDest(List<Integer>[]graph,intnode,intdest,Color[]states) { |
| 61 | + |
| 62 | +// If the state is GRAY, this is a backward edge and hence, it creates a loop. |
| 63 | +if (states[node]!=null) { |
| 64 | +return states[node]==Color.BLACK; |
| 65 | + } |
| 66 | + |
| 67 | +// If this is a leaf node, it should be equal to the destination. |
| 68 | +if (graph[node].isEmpty()) { |
| 69 | +return node== dest; |
| 70 | + } |
| 71 | + |
| 72 | +// Now, we are processing this node. So we mark it as GRAY |
| 73 | + states[node]=Color.GRAY; |
| 74 | + |
| 75 | +for (int next: graph[node]) { |
| 76 | + |
| 77 | +// If we get a `false` from any recursive call on the neighbors, we short circuit and return from there. |
| 78 | +if (!leadsToDest(graph, next, dest, states)) { |
| 79 | +returnfalse; |
| 80 | + } |
| 81 | + } |
| 82 | + |
| 83 | +// Recursive processing done for the node. We mark it BLACK |
| 84 | + states[node]=Color.BLACK; |
| 85 | +returntrue; |
| 86 | + } |
| 87 | + |
| 88 | +privateList<Integer>[]buildDigraph(intn,int[][]edges) { |
| 89 | +List<Integer>[] graph=newList[n]; |
| 90 | +for (int i=0; i< n; i++) { |
| 91 | + graph[i]=newArrayList<>(); |
| 92 | + } |
| 93 | + |
| 94 | +for (int[] edge: edges) { |
| 95 | + graph[edge[0]].add(edge[1]); |
| 96 | + } |
| 97 | + |
| 98 | +return graph; |
| 99 | + } |
| 100 | +} |
| 101 | +``` |
| 102 | + |
| 103 | +```cpp |
| 104 | +classSolution { |
| 105 | +public: |
| 106 | + static const int GRAY = 1; |
| 107 | + static const int BLACK = 2; |
| 108 | + |
| 109 | + bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) { |
| 110 | + vector<vector<int>> graph = buildDigraph(n, edges); |
| 111 | + vector<int> states(n, 0); |
| 112 | + return leadsToDest(graph, source, destination, states); |
| 113 | + } |
| 114 | + |
| 115 | +private: |
| 116 | + bool leadsToDest(vector<vector<int>>& graph, int node, int dest, vector<int>& states) { |
| 117 | + if (states[node] != 0) { |
| 118 | + return states[node] == BLACK; |
| 119 | + } |
| 120 | + if (graph[node].size() == 0) { |
| 121 | + return node == dest; |
| 122 | + } |
| 123 | + states[node] = GRAY; |
| 124 | + for (int next_node : graph[node]) { |
| 125 | + if (!leadsToDest(graph, next_node, dest, states)) { |
| 126 | + return false; |
| 127 | + } |
| 128 | + } |
| 129 | + states[node] = BLACK; |
| 130 | + return true; |
| 131 | + } |
| 132 | + |
| 133 | + vector<vector<int>> buildDigraph(int n, vector<vector<int>>& edges) { |
| 134 | + vector<vector<int>> graph(n); |
| 135 | + for (auto& edge : edges) { |
| 136 | + graph[edge[0]].push_back(edge[1]); |
| 137 | + } |
| 138 | + return graph; |
| 139 | + } |
| 140 | +}; |
| 141 | +``` |
| 142 | +
|
| 143 | +```javascript |
| 144 | +class Solution { |
| 145 | + static GRAY = 1; |
| 146 | + static BLACK = 2; |
| 147 | +
|
| 148 | + /** |
| 149 | + * @param {number} n |
| 150 | + * @param {number[][]} edges |
| 151 | + * @param {number} source |
| 152 | + * @param {number} destination |
| 153 | + * @return {boolean} |
| 154 | + */ |
| 155 | + leadsToDestination(n, edges, source, destination) { |
| 156 | + const graph = this.buildDigraph(n, edges); |
| 157 | + const states = new Array(n).fill(null); |
| 158 | + return this.leadsToDest(graph, source, destination, states); |
| 159 | + } |
| 160 | +
|
| 161 | + /** |
| 162 | + * @param {number[][]} graph |
| 163 | + * @param {number} node |
| 164 | + * @param {number} dest |
| 165 | + * @param {(number|null)[]} states |
| 166 | + * @return {boolean} |
| 167 | + */ |
| 168 | + leadsToDest(graph, node, dest, states) { |
| 169 | + if (states[node] !== null) { |
| 170 | + return states[node] === Solution.BLACK; |
| 171 | + } |
| 172 | + if (graph[node].length === 0) { |
| 173 | + return node === dest; |
| 174 | + } |
| 175 | + states[node] = Solution.GRAY; |
| 176 | + for (const next_node of graph[node]) { |
| 177 | + if (!this.leadsToDest(graph, next_node, dest, states)) { |
| 178 | + return false; |
| 179 | + } |
| 180 | + } |
| 181 | + states[node] = Solution.BLACK; |
| 182 | + return true; |
| 183 | + } |
| 184 | +
|
| 185 | + /** |
| 186 | + * @param {number} n |
| 187 | + * @param {number[][]} edges |
| 188 | + * @return {number[][]} |
| 189 | + */ |
| 190 | + buildDigraph(n, edges) { |
| 191 | + const graph = Array.from({ length: n }, () => []); |
| 192 | + for (const edge of edges) { |
| 193 | + graph[edge[0]].push(edge[1]); |
| 194 | + } |
| 195 | + return graph; |
| 196 | + } |
| 197 | +} |
| 198 | +``` |
| 199 | + |
| 200 | +::tabs-end |
| 201 | + |
| 202 | +###Time & Space Complexity |
| 203 | + |
| 204 | +- Time complexity: |
| 205 | +- Typically for an entire DFS over an input graph, it takes $O(V + E)$ where $V$ represents the number of vertices in the graph and likewise, $E$ represents the number of edges in the graph. In the worst case $E$ can be $O(V^2)$ in case each vertex is connected to every other vertex in the graph. However even in the worst case, we will end up discovering a cycle very early on and prune the recursion tree. If we were to traverse the entire graph, then the complexity would be $O(V^2)$ as the $O(E)$ part would dominate. However, due to pruning and backtracking in case of cycle detection, we end up with an overall time complexity of $O(V)$. |
| 206 | + |
| 207 | +- Space complexity: $O(V + E)$ |
| 208 | +- Where $O(E)$ is occupied by the adjacency list and $O(V)$ is occupied by the recursion stack and the color states. |
| 209 | + |
| 210 | +> Where $V$ represents the number of vertices in the graphand $E$ represents the number of edges in the graph. |
| 211 | + |
| 212 | +--- |
| 213 | + |
| 214 | +### Whynot Breadth-First Search? |
| 215 | + |
| 216 | +Fromthis [Stack Overflow](https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs) answer: |
| 217 | + |
| 218 | +> A BFS could be reasonableif the graph isundirected (be my guest at showing an efficient algorithm using BFS that would report the cycles in a directed graph!), where each cross edge defines a cycle (edge going from a node to an already visited node). If the cross edge is`{v1, v2}`, and the root (in the BFS tree) that contains those nodes is`r`, then the cycle is`r ~ v1 - v2 ~ r` (~ is a path, - a single edge), which can be reported almost as easily as in DFS. |
| 219 | +> |
| 220 | +>The only reason to use a BFS would be if you know your (undirected) graph is going to have long paths and small path cover (in other words, deep and narrow). In that case, BFS would require proportionally less memory for its queue than DFS' stack (both still linear of course). |
| 221 | +> |
| 222 | +>In all other cases, DFS is clearly the winner. |