Scribd
Upload
2 views4 pages

GraphProblems Java Code

The document contains a Java program that implements two graph-related problems: checking if a path exists between two nodes and finding nodes at a specific distance from a starting node. It uses depth-first search (DFS) for path existence and breadth-first search (BFS) for finding nodes at K distance. The main method facilitates user input for the number of nodes, edges, and specific queries for both problems.

Uploaded by

Naman Jain
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

GraphProblems Java Code

The document contains a Java program that implements two graph-related problems: checking if a path exists between two nodes and finding nodes at a specific distance from a starting node. It uses depth-first search (DFS) for path existence and breadth-first search (BFS) for finding nodes at K distance. The main method facilitates user input for the number of nodes, edges, and specific queries for both problems.

Uploaded by

Naman Jain
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

GraphProblems.

java - Java Code for PS1


and PS2
import [Link].*;

public class GraphProblems {

// ---------- PS1: Path Exists ----------

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

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

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

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] && dfs(graph, neighbor, end, visited))
{

return true;

return false;

// ---------- PS2: Nodes at K Distance ----------

public static List<Integer> nodesAtKDistance(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) {

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

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

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 node = [Link]();

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

if(!visited[neighbor]) {

visited[neighbor] = true;

[Link](neighbor);

level++;

return new ArrayList<>(queue);

// ---------- Main Method ----------

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Enter number of nodes:");

int n = [Link]();

[Link]("Enter number of edges:");

int m = [Link]();

int[][] edges = new int[m][2];

[Link]("Enter edges (u v):");

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

edges[i][0] = [Link]();
edges[i][1] = [Link]();

[Link]("\n--- PS1: Check Path Existence ---");

[Link]("Enter start node: ");

int start1 = [Link]();

[Link]("Enter end node: ");

int end1 = [Link]();

boolean pathExists = validPath(n, edges, start1, end1);

[Link]("Path exists: " + pathExists);

[Link]("\n--- PS2: Nodes at K Distance ---");

[Link]("Enter start node: ");

int start2 = [Link]();

[Link]("Enter distance k: ");

int k = [Link]();

List<Integer> result = nodesAtKDistance(n, edges, start2, k);

[Link]("Nodes at distance " + k + ": " + result);

You might also like