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:
        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 
    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); 
        } 
    } 
      
    // if required element is not found in the graph 
    return false; 
}