This is a java program to construct a undirected graph and check whether path exists between two vertices, if it exists class return true, false otherwise. Class implements standard Breadth First Search algorithm to traverse from given source node to destination node.
Here is the source code of the Java Program to Find Whether a Path Exists Between 2 Given Nodes. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a sample program to check that there exists a path between source node and destination node import java.util.HashMap; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.Map; import java.util.Scanner; import java.util.Set; public class Path_Between_Nodes { private Map<String, LinkedHashSet<String>> map = new HashMap(); public void addEdge(String node1, String node2) { LinkedHashSet<String> adjacent = map.get(node1); if (adjacent == null) { adjacent = new LinkedHashSet(); map.put(node1, adjacent); } adjacent.add(node2); } public void addTwoWayVertex(String node1, String node2) { addEdge(node1, node2); addEdge(node2, node1); } public boolean isConnected(String node1, String node2) { Set adjacent = map.get(node1); if (adjacent == null) { return false; } return adjacent.contains(node2); } public LinkedList<String> adjacentNodes(String last) { LinkedHashSet<String> adjacent = map.get(last); if (adjacent == null) { return new LinkedList(); } return new LinkedList<String>(adjacent); } private static String START; private static String END; private static boolean flag; public static void main(String[] args) { // this graph is directional Path_Between_Nodes graph = new Path_Between_Nodes(); // graph.addEdge("A", "B"); graph.addEdge("A", "C"); graph.addEdge("B", "A"); graph.addEdge("B", "D"); graph.addEdge("B", "E"); graph.addEdge("B", "F"); graph.addEdge("C", "A"); graph.addEdge("C", "E"); graph.addEdge("C", "F"); graph.addEdge("D", "B"); graph.addEdge("E", "C"); graph.addEdge("E", "F"); // graph.addEdge("F", "B"); graph.addEdge("F", "C"); graph.addEdge("F", "E"); LinkedList<String> visited = new LinkedList(); System.out.println("Enter the source node:"); Scanner sc = new Scanner(System.in); START = sc.next(); System.out.println("Enter the destination node:"); END = sc.next(); visited.add(START); new Path_Between_Nodes().breadthFirst(graph, visited); sc.close(); } private void breadthFirst(Path_Between_Nodes graph, LinkedList<String> visited) { LinkedList<String> nodes = graph.adjacentNodes(visited.getLast()); for (String node : nodes) { if (visited.contains(node)) { continue; } if (node.equals(END)) { visited.add(node); printPath(visited); flag = true; visited.removeLast(); break; } } for (String node : nodes) { if (visited.contains(node) || node.equals(END)) { continue; } visited.addLast(node); breadthFirst(graph, visited); visited.removeLast(); } if (flag == false) { System.out.println("No path Exists between " + START + " and " + END); flag = true; } } private void printPath(LinkedList<String> visited) { if (flag == false) System.out.println("Yes there exists a path between " + START + " and " + END); for (String node : visited) { System.out.print(node); System.out.print(" "); } System.out.println(); } }
Output:
$ javac Path_Between_Nodes.java $ java Path_Between_Nodes Enter the source node: E Enter the destination node: B No path Exists between E and B Enter the source node: A Enter the destination node: E Yes there exists a path between A and E A C E A C F E
Related posts:
XML-Based Injection in Spring
How to Remove the Last Character of a String?
Test a REST API with Java
Jackson – Bidirectional Relationships
Custom Exception trong Java
A Guide to ConcurrentMap
Java Program to Implement Control Table
Using a List of Values in a JdbcTemplate IN Clause
Basic Authentication with the RestTemplate
Immutable Map Implementations in Java
@Before vs @BeforeClass vs @BeforeEach vs @BeforeAll
Registration – Password Strength and Rules
Spring RequestMapping
Java Web Services – Jersey JAX-RS – REST và sử dụng REST API testing tools với Postman
Setting the Java Version in Maven
Spring Cloud Connectors and Heroku
How to Read HTTP Headers in Spring REST Controllers
So sánh ArrayList và Vector trong Java
Java Program to Implement ArrayList API
Java Program to Implement Leftist Heap
Java – Create a File
Java Program to Implement Hamiltonian Cycle Algorithm
Spring Security and OpenID Connect
Introduction to Spring Cloud OpenFeign
Registration – Activate a New Account by Email
Java Web Services – JAX-WS – SOAP
Java Program to Find Hamiltonian Cycle in an UnWeighted Graph
Java Program to Implement Bresenham Line Algorithm
Performance Difference Between save() and saveAll() in Spring Data
Exception Handling in Java
The Registration API becomes RESTful
Jackson vs Gson