Scribd
Upload
2 views3 pages

Solution

The document contains two programming problems related to undirected graphs. The first problem involves determining if there is a path between two nodes using a breadth-first search approach, while the second problem requires finding all nodes that are exactly k edges away from a starting node. Both solutions utilize graph traversal techniques and adjacency lists to achieve their objectives.

Uploaded by

learning.new.skills.13
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 views3 pages

Solution

The document contains two programming problems related to undirected graphs. The first problem involves determining if there is a path between two nodes using a breadth-first search approach, while the second problem requires finding all nodes that are exactly k edges away from a starting node. Both solutions utilize graph traversal techniques and adjacency lists to achieve their objectives.

Uploaded by

learning.new.skills.13
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

Solution:

class Solution {

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

if([Link] == 0) return true;

boolean[] visited = new boolean[n];

boolean flag = true;

visited[start] = true;

while(flag){

flag = false;

for(int[] edge : edges){

if(visited[edge[0]] != visited[edge[1]]){

visited[edge[0]] = true;

visited[edge[1]] = true;

flag = true;

if(visited[end]) return true;

return false;

}
PS2: In an undirected graph 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

solution:

public class KDistanceNodes {

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

// Build the graph using adjacency list

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

for (int i = 0; i < n; i++) [Link](new ArrayList<>());

for (int[] edge : edges) {

[Link](edge[0]).add(edge[1]);

[Link](edge[1]).add(edge[0]); // undirected

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

boolean[] visited = new boolean[n];

[Link](start);

visited[start] = true;

int level = 0;

while (![Link]()) {

int size = [Link]();

if (level == k) break;

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);

You might also like