# 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

- input:
- 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**.

- output:
- return 1 if we can start from
**1**and end at**A**else return 0.

- return 1 if we can start from

### 0.1. Examples

Consider the inputs:

*A = 5B = [[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

### 1.0. Cycles

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.

### 1.1. Algorithms

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

### 2.0. Code

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

- Time:
`O(A)`

, where A is the number of nodes in the graph in our case - Space:
`O(A)`

, since the height of the recursion call stack will be the number of nodes.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.

Please write a Proof for this