Find if Path Exists in Graph
The task is to determine if there is a valid path from a given source vertex to a destination vertex in a graph. The vertices are labeled from 0 to n1. The edges are given in a 2D integer array where each subarray represents a bidirectional edge between two vertices.
You can approach this problem using a technique called DepthFirst Search (DFS). This technique is used to traverse or search through a graph in a depthward motion and uses a stack data structure to remember to get the next vertex to start a search when a deadend occurs in any iteration.
Here is a step by step approach to solve this problem:
Create an adjacency list to represent the graph. An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.
Use DepthFirst Search (DFS) to find a path from the source to the destination. Starting from the source, recursively visit each node that is adjacent to the current node and not already visited.
If you reach the destination node during the DFS traversal, that means there is a path from source to destination. So, return
True
.If the DFS ends without visiting the destination, that means no valid path exists, and you can return
False
.
Here is the Python implementation:


This algorithm works within the given constraints. The time complexity is O(n + e) where n is the number of vertices and e is the number of edges in the graph. The space complexity is O(n + e) to store the adjacency list and the visited set.