Find If Path Exists In Graph - Leetcode Solution

Problem statement:

Given a graph represented by an adjacency matrix graph[][] and two vertices source and destination. Your task is to check if there exists a path from source to destination.

Solution:

The given problem can be solved using Depth-First-Search (DFS) or Breadth-First-Search (BFS) algorithms. In this solution, we will use BFS to solve the problem.

We need to traverse the graph starting from the source node and mark all the nodes that can be reached from the source node. We can traverse the graph using a queue as it will follow a level-by-level traversal.

Algorithm:

1. Create a queue and push the source node into it.
2. Create a visited array and initialize all the elements to false.
3. While the queue is not empty:
   • Retrieve the head of the queue and mark it as visited.
   • Check if the retrieved node is the destination node. If true, return true as there exists a path from source to destination.
   • Otherwise, traverse all the adjacent nodes of the retrieved node that are not visited and push them into the queue.
4. If we can't find the destination node after traversing all nodes, return false.

Pseudo code:

isPathExistsBFS(graph[][], source, destination):
    queue = createQueue
    visited = createVisitedArray
    push queue with source
    visited[source] = true
    
    while queue is not empty:
        node = pop queue
        if node == destination:
            return true
        for each adjacent node of the node:
            if not visited[adjacent]:
                push adjacent into queue
                visited[adjacent] = true
    return false

Time Complexity:

In the worst case, we need to traverse all the nodes of the given graph and for each node, we need to look at its adjacency matrix which is O(N^2) operations. Hence the time complexity of this solution is O(N^2).

Space Complexity:

The space complexity of this solution is O(N) as we need to store the visited array and queue.

Code:

from queue import Queue

def isPathExistsBFS(graph, source, destination):
    N = len(graph)
    q = Queue()
    visited = [False] * N
    
    q.put(source)
    visited[source] = True
    
    while not q.empty():
        node = q.get()
        if node == destination:
            return True
        for adjacent in range(N):
            if graph[node][adjacent] == 1 and not visited[adjacent]:
                q.put(adjacent)
                visited[adjacent] = True
    return False

This code has been written in Python 3 and it uses the built-in Queue module to implement the queue required for BFS. In line 10, we are pushing the source node into the queue using the put() method and in line 19, we are retrieving the head of the queue using the get() method. In line 14, we are checking if the adjacent node hasn't been visited and in line 15, we are marking it as visited using the visited array.

1