# Solution For Find If Path Exists In 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:

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

“`python
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
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.

## Step by Step Implementation For Find If Path Exists In Graph

```There are many possible solutions to this problem, but one possible Java solution is as follows:

1) Create a graph data structure to represent the input graph. This can be done using an adjacency list or adjacency matrix.

2) Use a depth-first search or breadth-first search algorithm to traverse the graph and check if a path exists between the two given nodes.

3) If a path is found, return true. Otherwise, return false.

Here is some sample code to get you started:

import java.util.*;

public class Solution {

public static boolean findPath(int[][] graph, int start, int end) {

// TODO: implement this function

}

public static void main(String[] args) {

int[][] graph = {{1,2}, {2,3}, {3,4}, {4,5}};

int start = 1;

int end = 5;

boolean pathExists = findPath(graph, start, end);

if (pathExists) {

System.out.println("There is a path between " + start + " and " + end + ".");

} else {

System.out.println("There is no path between " + start + " and " + end + ".");

}

}

}```
```def find_if_path_exists_in_graph(graph, start, end):
# create a queue to store nodes that need to be explored
queue = []
# create a set to store nodes that have been visited
visited = set()
# add the starting node to the queue
queue.append(start)
# add the starting node to the set of visited nodes
# while the queue is not empty
while queue:
# get the first node in the queue
node = queue.pop(0)
# if the node is the end node, then a path exists
if node == end:
return True
# for each neighbor of the node
for neighbor in graph[node]:
# if the neighbor has not been visited
if neighbor not in visited:
# add the neighbor to the queue
queue.append(neighbor)
# add the neighbor to the set of visited nodes
# if the end node was not reached, then a path does not exist
return False```
`Given a directed graph, design an algorithm to find out whether there is a route between two nodes.`
`There are many possible solutions to this problem. One approach would be to use a depth-first search algorithm to traverse the graph, starting from the source vertex. If the destination vertex is reached, then there is a path between the source and destination. Otherwise, there is no path.`
```public bool FindPathExists(int[][] graph, int start, int end)
{
// create a visited array
bool[] visited = new bool[graph.Length];

// create a stack
Stack stack = new Stack();

// push the start vertex into the stack
stack.Push(start);

// run till stack is not empty
while (stack.Count != 0)
{
// pop a vertex from stack
int curr = stack.Pop();

// if the popped element is the required element
// then return true
if (curr == end)
return true;

// if the element is not visited then mark it
// as visited and push it into the stack
if (!visited[curr])
{
visited[curr] = true;
foreach (var i in graph[curr])
stack.Push(i);
}
}