fork download
copy 
  1. import java.util.HashMap;
  2. import java.util.LinkedHashSet;
  3. import java.util.LinkedList;
  4. import java.util.Map;
  5. import java.util.Set;
  6. import java.util.LinkedList;
  7.  
  8. class Graph {
  9.     private Map<String, LinkedHashSet<String>> map = new HashMap();
  10.  
  11.     public void addEdge(String node1, String node2) {
  12.         LinkedHashSet<String> adjacent = map.get(node1);
  13.         if(adjacent==null) {
  14.             adjacent = new LinkedHashSet();
  15.             map.put(node1, adjacent);
  16.         }
  17.         adjacent.add(node2);
  18.     }
  19.  
  20.     public void addTwoWayVertex(String node1, String node2) {
  21.         addEdge(node1, node2);
  22.         addEdge(node2, node1);
  23.     }
  24.  
  25.     public boolean isConnected(String node1, String node2) {
  26.         Set adjacent = map.get(node1);
  27.         if(adjacent==null) {
  28.             return false;
  29.         }
  30.         return adjacent.contains(node2);
  31.     }
  32.  
  33.     public LinkedList<String> adjacentNodes(String last) {
  34.         LinkedHashSet<String> adjacent = map.get(last);
  35.         if(adjacent==null) {
  36.             return new LinkedList();
  37.         }
  38.         return new LinkedList<String>(adjacent);
  39.     }
  40. }
  41.  
  42.  
  43.  
  44.  
  45.  
  46. class Search {
  47.  
  48.     private static final String START = "A";
  49.     private static final String END = "E";
  50.  
  51.     public static void main(String[] args) {
  52.         // this graph is directional
  53.         Graph graph = new Graph();
  54.         graph.addEdge("A", "B");
  55.         graph.addEdge("D", "B");
  56.         graph.addEdge("B", "C");
  57.         graph.addEdge("C", "D");
  58.         graph.addEdge("D", "E"); // this is the only one-way connection
  59.         /*graph.addEdge("B", "F");
  60.         graph.addEdge("C", "A");
  61.         graph.addEdge("C", "E");
  62.         graph.addEdge("C", "F");
  63.         graph.addEdge("D", "B");
  64.         graph.addEdge("E", "C");
  65.         graph.addEdge("E", "F");
  66.         graph.addEdge("F", "B");
  67.         graph.addEdge("F", "C");
  68.         graph.addEdge("F", "E");*/
  69.         LinkedList<String> visited = new LinkedList();
  70.         visited.add(START);
  71.         new Search().breadthFirst(graph, visited);
  72.     }
  73.  
  74.     private void breadthFirst(Graph graph, LinkedList<String> visited) {
  75.         LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
  76.         // examine adjacent nodes
  77.         for (String node : nodes) {
  78.             if (visited.contains(node)) {
  79.                 continue;
  80.             }
  81.             if (node.equals(END)) {
  82.                 visited.add(node);
  83.                 printPath(visited);
  84.                 visited.removeLast();
  85.                 break;
  86.             }
  87.         }
  88.         // in breadth-first, recursion needs to come after visiting adjacent nodes
  89.         for (String node : nodes) {
  90.             if (visited.contains(node) || node.equals(END)) {
  91.                 continue;
  92.             }
  93.             visited.addLast(node);
  94.             breadthFirst(graph, visited);
  95.             visited.removeLast();
  96.         }
  97.     }
  98.  
  99.     private void printPath(LinkedList<String> visited) {
  100.         for (String node : visited) {
  101.             System.out.print(node);
  102.             System.out.print(" ");
  103.         }
  104.         System.out.println();
  105.     }
  106. }
Success #stdin #stdout 0.08s 51300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
A B C D E
https://ideone.com/JyfJpR
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!