Find if Path Exists in Graph

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n-1 (inclusive). The edges in the graph are represented as 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex start to vertex end.

Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

Approach

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class FindPathExist {
    public static void main(String[] args) {

        int n = 3;
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
        int start = 0, end = 2;

        System.out.println(validPath(n, edges, start, end));

    }

    static boolean flag = false;
    static Map<Integer, List<Integer>> adj;
    static Set<Integer> visited;

    public static boolean validPath(int n, int[][] edges, 
            int start, int end) {

        // if start is same as end then return true.
        if (start == end)
            return true;

        adj = new HashMap<>();
        visited = new HashSet<>();

        // Initializing the adjacency list and then adding
        // bidirectional edges to it

        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<>());
        }

        // add edges into the adjacency list
        for (int[] i : edges) {
            adj.get(i[0]).add(i[1]);
            adj.get(i[1]).add(i[0]);
        }

        // we start by marking start as visited
        visited.add(start);
        // and then we traverse using dfs
        dfs(adj.get(start), start, end);

        // at the end all we need to do is return
        return flag;
    }

    public static void dfs(List<Integer> temp, int node,
        int end) {
        if (temp == null)
            return;

        if (node == end) {
            flag = true;
            return;
        }
        // iterate through all the neighbors of current node
        for (int i : temp) {

            // if the neighbor is unvisited then just
            // visit its list too
            if (!visited.contains(i)) {
                visited.add(i);
                dfs(adj.get(i), i, end);
            }
        }

    }

}

C++

#include <bits/stdc++.h>
using namespace std;

bool flag = false;

void dfs(int node, int end, vector<bool> &vis,
      vector<vector<int>> &adj)
{

    //if current node is the end node then
    //we set flag as true as we found a path from start to end
    //and return from the function
    if (node == end)
    {
        flag = true;
        return;
    }

    //mark current node as visited so that we cannot
    //traverse the same node again and again.
    vis[node] = true;

    //iterate through all th adjacent nodes of current node
    for (int it : adj[node])
    {
        //if not visited then call for dfs
        //recursively
        if (vis[it] == false)
            dfs(it, end, vis, adj);
    }
}

bool validPath(int n, vector<vector<int>> &edges, 
       int start, int end)
{

    vector<vector<int>> adj(n);

    //create a visisted array
    vector<bool> vis(n, false);

    //create a graph from the given edges
    for (int i = 0; i < edges.size(); i++)
    {

        int u = edges[i][0];
        int v = edges[i][1];

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //call for dfs
    dfs(start, end, vis, adj);

    return flag;
}

int main()
{
    int n = 3;
    vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 0}};
    int start = 0, end = 2;

    if (validPath(n, edges, start, end))
        cout << "true\n";
    else
        cout << "false\n";

    return 0;
}