manthanthakker40

BFS and DFS Graph traversal Techniques

Jan 3rd, 2017
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.15 KB | None | 0 0
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package graphstraversal;
  7.  
  8. import java.util.LinkedList;
  9. import java.util.HashMap;
  10. import java.util.LinkedList;
  11. import java.util.Scanner;
  12. import javax.swing.JFrame;
  13. import javax.swing.ImageIcon;
  14. import javax.swing.JLabel;
  15.  
  16. /**
  17.  *
  18.  * @author manth
  19.  */
  20. public class GraphsTraversal {
  21.  
  22.  /**
  23.   * @param args the command line arguments
  24.   */
  25.  
  26.  static HashMap < Integer, LinkedList > graph = new HashMap < > ();
  27.  static LinkedList < Integer > queue = new LinkedList < > ();
  28.  static LinkedList < Integer > visited = new LinkedList < > ();
  29.  static LinkedList < Integer > stack = new LinkedList < > ();
  30.  public static void main(String[] args) {
  31.   Scanner sc = new Scanner(System.in);
  32.   build_graph();
  33.   JFrame frame = new JFrame();
  34.   ImageIcon icon = new ImageIcon("graph.jpg");
  35.   JLabel label = new JLabel(icon);
  36.   frame.add(label);
  37.   frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  38.   frame.pack();
  39.   frame.setVisible(true);
  40.   System.out.println("Enter Starting node_id (any from 1-10)  ");
  41.   int start_v = Integer.parseInt(sc.nextLine());
  42.   System.out.println("Enter which traversal technique ?\n1.BFS\n2.DFS");
  43.   switch (Integer.parseInt(sc.nextLine())) {
  44.    case 1:
  45.     bfs(start_v);
  46.     break;
  47.    case 2:
  48.     dfs(start_v);
  49.     break;
  50.   }
  51.  
  52.  }
  53.  public static void dfs(int starting_v) {
  54.   push(starting_v);
  55.   visited.add(starting_v);
  56.   while (!stack.isEmpty()) {
  57.    int v = pop();
  58.    if (!graph.get(v).isEmpty()) {
  59.     LinkedList < Integer > directly_connected = graph.get(v);
  60.     for (Integer v1: directly_connected) {
  61.      if (!visited.contains(v1)) {
  62.       push(v1);
  63.       visited.addLast(v1);
  64.      }
  65.     }
  66.     System.out.print(v + " ");
  67.    }
  68.   }
  69.  
  70.  }
  71.  public static void push(int v) {
  72.   stack.addFirst(v);
  73.  }
  74.  public static int pop() {
  75.   return stack.removeFirst();
  76.  }
  77.  public static void bfs(int starting_v) {
  78.   enque(starting_v);
  79.   visited.add(starting_v);
  80.   while (!queue.isEmpty()) {
  81.    int v = dequeue();
  82.    if (graph.get(v) != null)
  83.     add_All(graph.get(v));
  84.    System.out.print(v + " ");
  85.  
  86.   }
  87.  }
  88.  
  89.  public static void add_All(LinkedList < Integer > directly_connected) {
  90.   for (int v: directly_connected) {
  91.    if (!visited.contains(v)) {
  92.     enque(v);
  93.     visited.addLast(v);
  94.    }
  95.   }
  96.  }
  97.  public static void enque(int v) {
  98.   queue.addLast(v);
  99.  }
  100.  public static int dequeue() {
  101.   return queue.removeFirst();
  102.  }
  103.  public static void build_graph() {
  104.   LinkedList l = new LinkedList();
  105.   l.add(2);
  106.   l.add(3);
  107.   l.add(4);
  108.   graph.put(1, l);
  109.   l = new LinkedList();
  110.   l.add(5);
  111.   l.add(6);
  112.   l.add(7);
  113.   l.add(1);
  114.   graph.put(2, l);
  115.   l = new LinkedList();
  116.   l.add(8);
  117.   l.add(1);
  118.   graph.put(3, l);
  119.   l = new LinkedList();
  120.   l.add(9);
  121.   l.add(10);
  122.   l.add(1);
  123.   graph.put(4, l);
  124.   l = new LinkedList();
  125.   l.add(2);
  126.   graph.put(5, l);
  127.   graph.put(6, l);
  128.   graph.put(7, l);
  129.   l = new LinkedList();
  130.   l.add(3);
  131.   graph.put(8, l);
  132.   l = new LinkedList();
  133.   l.add(4);
  134.   graph.put(9, l);
  135.   graph.put(10, l);
  136.  }
  137. }
Advertisement
Add Comment
Please, Sign In to add comment