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:
Cài đặt và sử dụng Swagger UI
Spring Data JPA and Null Parameters
Hướng dẫn Java Design Pattern – Facade
Java Program to Implement Repeated Squaring Algorithm
Hướng dẫn Java Design Pattern – Iterator
Java Program to Generate Random Numbers Using Probability Distribution Function
Spring REST with a Zuul Proxy
Java Program to Implement the Program Used in grep/egrep/fgrep
REST Web service: Basic Authentication trong Jersey 2.x
ClassNotFoundException vs NoClassDefFoundError
Spring Data JPA @Query
Java Program to Create a Balanced Binary Tree of the Incoming Data
Spring Boot - Creating Docker Image
Java Streams vs Vavr Streams
Introduction to the Java NIO2 File API
CharSequence vs. String in Java
Java Program to Find Number of Spanning Trees in a Complete Bipartite Graph
How to Get All Dates Between Two Dates?
Iterating over Enum Values in Java
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Java Program to Implement Sieve Of Eratosthenes
Write/Read cookies using HTTP and Read a file from the internet
Java – String to Reader
Toán tử instanceof trong java
Java Program to Check Whether a Given Point is in a Given Polygon
Supplier trong Java 8
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Java Program to Implement Best-First Search
Get the workstation name or IP
Guide to Java Instrumentation
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java