SHARE
TWEET

Untitled

a guest Mar 15th, 2019 119 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.HashMap;
  5. import java.util.Iterator;
  6. import java.util.LinkedList;
  7. import java.util.Queue;
  8.  
  9. public class Main {
  10.  
  11.     public static void BFS(HashMap<String, Vertax> graph, String vertax) {
  12.         Queue<String> queue = new LinkedList<String>();
  13.         queue.add(vertax);
  14.         graph.get(vertax).flag = true;
  15.  
  16.         while (!queue.isEmpty()) {
  17.             String value = queue.poll();
  18.             System.out.print(value + " ");
  19.             Vertax v = graph.get(value);
  20.             Iterator<String> iter = v.next.iterator();
  21.             while (iter.hasNext()) {
  22.                 String next_value = iter.next();
  23.                 if (graph.get(next_value).flag == false) {
  24.                     queue.add(next_value);
  25.                     graph.get(next_value).flag = true;
  26.                 }
  27.             }
  28.         }
  29.     }
  30.  
  31.     public static void main(String[] args) {
  32.         HashMap<String, Vertax> graph = new HashMap<String, Vertax>();
  33.  
  34.         try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
  35.             String line;
  36.             while ((line = br.readLine()) != null) {
  37.                 String[] tokens = line.split(" ");
  38.                 String value = tokens[0];
  39.                 Vertax vertax = new Vertax(value);
  40.                 graph.put(value, vertax);
  41.                 for (int i = 1; i < tokens.length; i++) {
  42.                     vertax.next.add(tokens[i]);
  43.                 }
  44.             }
  45.         } catch (Exception e) {
  46.             e.printStackTrace();
  47.         }
  48.         BFS(graph, "A");
  49.     }
  50.  
  51. }
  52.  
  53. class Vertax {
  54.     String value;
  55.     boolean flag;
  56.     LinkedList<String> next;
  57.  
  58.     public Vertax(String value) {
  59.         this.value = value;
  60.         this.flag = false;
  61.         next = new LinkedList<String>();
  62.     }
  63.  
  64. }
  65.  
  66. /* inputs on console of eclipse
  67. A B S
  68. B A
  69. C D E F S
  70. D C
  71. E C H
  72. F C G
  73. G S H
  74. H E G
  75. S A C G
  76. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top