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.
 Path in Directed Graph: explaining the input output format
Path in Directed Graph: explaining the input output format

0.1. Examples

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.

 Path in Directed Graph: an example test case with answer 0
Path in Directed Graph: an example test case with answer 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.

 Path in Directed Graph: converting edge list to adjacency list
Path in Directed Graph: converting edge list to adjacency list

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.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

      A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

      Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

      To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

      Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

      This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

      Understanding why solar energy consultants assist clients via Matthew D’Agati.
      Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.