Scribd
Upload
2 views4 pages

Solution Java

The document contains two problems related to undirected graphs. The first problem involves determining if there is a path between two nodes using depth-first search, resulting in a false output for the given example. The second problem requires finding all nodes that are exactly k edges away from a starting node using breadth-first search, producing the output [3, 4, 5] for the provided example.

Uploaded by

rishavatsa9920
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views4 pages

Solution Java

The document contains two problems related to undirected graphs. The first problem involves determining if there is a path between two nodes using depth-first search, resulting in a false output for the given example. The second problem requires finding all nodes that are exactly k edges away from a starting node using breadth-first search, producing the output [3, 4, 5] for the provided example.

Uploaded by

rishavatsa9920
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

PS1: In an undirected graph with n nodes and a list of edges, determine if there is a path

between two given nodes start and end. Sample: n=6 edges = {(0,1),(0,2),(3,5),(5,4),(4,3)}
start = 0 end = 5 Output: false
Solution :

import [Link].*;

public class GraphPathFinder

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

List<List<Integer>> graph = new ArrayList<>();

for(int i = 0; i < n; i++) {

[Link](new ArrayList<>());

for(int[] edge : edges) {

int u = edge[0], v = edge[1];

[Link](u).add(v);

[Link](v).add(u); // undirected

boolean[] visited = new boolean[n];

return dfs(graph, start, end, visited);

private static boolean dfs(List<List<Integer>> graph, int current, int end, boolean[] visited) {

if (current == end) return true;

visited[current] = true;

for (int neighbor : [Link](current)) {

if (!visited[neighbor]) {

if (dfs(graph, neighbor, end, visited)) {

return true;

}
}

return false;

public static void main(String[] args) {

int n = 6;

int[][] edges = {

{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}

};

int start = 0, end = 5;

[Link](validPath(n, edges, start, end));

Output: false

PS2: In an undirected raph with n nodes and a list of edges, and a starting node start,
return all nodes that are exactly k edges away from the starting node. the result can be
returned in any order. Sample: n=6 edges = {(0,1),(0,2),(1,3),(2,4),(2,5)} start = 0
k=2 output: [3,4,5]
Solution :
import [Link].*;

public class NodesAtKDistance {

public static List<Integer> nodesAtDistanceK(int n, int[][] edges, int start, int k) {

List<List<Integer>> graph = new ArrayList<>();

for (int i = 0; i < n; i++) {

[Link](new ArrayList<>());

for (int[] edge : edges) {


int u = edge[0], v = edge[1];

[Link](u).add(v);

[Link](v).add(u); // Undirected

Queue<Integer> queue = new LinkedList<>();

boolean[] visited = new boolean[n];

int level = 0;

[Link](start);

visited[start] = true;

while (![Link]() && level < k) {

int size = [Link]();

for (int i = 0; i < size; i++) {

int curr = [Link]();

for (int neighbor : [Link](curr)) {

if (!visited[neighbor]) {

visited[neighbor] = true;

[Link](neighbor);

level++;

return new ArrayList<>(queue);

public static void main(String[] args) {

int n = 6;

int[][] edges = {
{0, 1}, {0, 2}, {1, 3}, {2, 4}, {2, 5}

};

int start = 0;

int k = 2;

List<Integer> result = nodesAtDistanceK(n, edges, start, k);

[Link](result);

Output: [3, 4, 5]

You might also like