Path in Directed Graph | InterviewBit | Solution Explained
I explain the solution to Path in Directed Graph in detail, along with visuals to help make things clear. Code in Python3 also added.
0. Path in Directed Graph: Problem Discussion
0.0. IO Format
- A is an integer, specifying the number of nodes
- B is a list of list of integers, specifying two nodes: from and to, saying that there is a directed edge from from to to.
- return 1 if we can start from 1 and end at A else return 0.
Consider the inputs:
A = 5
B = [[1, 2],[4, 1],[2, 4],[3, 4],[5, 2],[1, 3]]
In the case below, no matter what path we traverse, we will never be able to reach 5 from 1. This means that the answer is 0.
1. Path in Directed Graph: Observations & Logic
The test case above also hints at one issue that might occur: cycles in the graph! This means that an algorithm that does not keep a track of what nodes which it has visited already, will end up in an infinite loop.
That being said, what about the algorithms we have to use? In graph traversal questions, I often prefer writing DFS, since it is super small and easy to implement.
One small catch: In Python3, the recursion limit is set to 10**3. This means that test cases which are larger than 10**3 will end up causing an error – although everything else is perfect! In cases like these, we can manually change the recursion limit to 10**5 or whatever we require.
One other option is to use BFS, which will work out equally well.
1.2. Input Formatting
Regardless of what algorithm we choose to use: BFS or DFS, we must first get the adjacency list from the edge list format – allowing us to traverse the nodes easily. In terms of implementation, we have a dictionary of keys – which are the nodes from where we can go to the to nodes.
We can use the code snippet below to create the adjacency list, as shown in the diagram above.
adj = defaultdict(list) # a dict of list for x, y in B: adj[x].append(y)
2. Path in Directed Graph: Optimized Implementation
from collections import defaultdict import sys class Solution: def solve(self, A, B): sys.setrecursionlimit(2*10**5+2) def dfs(node): # base case if node == A: return True # if already seen, avoid this to avoid cycles if node in visited: return False # visit this node visited.add(node) # check if any of the returns is True - then return True return any(dfs(child) for child in adj[node]) adj = defaultdict(list) # a dict of list visited = set() # a set for O(1) addition and existence checking for x, y in B: adj[x].append(y) return int(dfs(1))
2.1. Complexity Analysis
O(A), where A is the number of nodes in the graph in our case
O(A), since the height of the recursion call stack will be the number of nodes.
June 13, 2022
June 13, 2022