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

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

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

## 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 visited.add(start) # 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 visited.add(neighbor) # 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 Stackstack = 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); } } // if required element is not found in the graph return false; }