## Similar Problems

Similar Problems not available

# Find If Path Exists In Graph - Leetcode Solution

## Companies:

LeetCode: Find If Path Exists In Graph Leetcode Solution

Difficulty: Easy

Topics: breadth-first-search union-find depth-first-search graph

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:

- Create a queue and push the source node into it.
- Create a visited array and initialize all the elements to false.
- 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.

- 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.

## Find If Path Exists In Graph Solution Code

`1`