Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
- package graphstraversal;
- import java.util.LinkedList;
- import java.util.HashMap;
- import java.util.LinkedList;
- import java.util.Scanner;
- import javax.swing.JFrame;
- import javax.swing.ImageIcon;
- import javax.swing.JLabel;
- /**
- *
- * @author manth
- */
- public class GraphsTraversal {
- /**
- * @param args the command line arguments
- */
- static HashMap < Integer, LinkedList > graph = new HashMap < > ();
- static LinkedList < Integer > queue = new LinkedList < > ();
- static LinkedList < Integer > visited = new LinkedList < > ();
- static LinkedList < Integer > stack = new LinkedList < > ();
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- build_graph();
- JFrame frame = new JFrame();
- ImageIcon icon = new ImageIcon("graph.jpg");
- JLabel label = new JLabel(icon);
- frame.add(label);
- frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
- frame.pack();
- frame.setVisible(true);
- System.out.println("Enter Starting node_id (any from 1-10) ");
- int start_v = Integer.parseInt(sc.nextLine());
- System.out.println("Enter which traversal technique ?\n1.BFS\n2.DFS");
- switch (Integer.parseInt(sc.nextLine())) {
- case 1:
- bfs(start_v);
- break;
- case 2:
- dfs(start_v);
- break;
- }
- }
- public static void dfs(int starting_v) {
- push(starting_v);
- visited.add(starting_v);
- while (!stack.isEmpty()) {
- int v = pop();
- if (!graph.get(v).isEmpty()) {
- LinkedList < Integer > directly_connected = graph.get(v);
- for (Integer v1: directly_connected) {
- if (!visited.contains(v1)) {
- push(v1);
- visited.addLast(v1);
- }
- }
- System.out.print(v + " ");
- }
- }
- }
- public static void push(int v) {
- stack.addFirst(v);
- }
- public static int pop() {
- return stack.removeFirst();
- }
- public static void bfs(int starting_v) {
- enque(starting_v);
- visited.add(starting_v);
- while (!queue.isEmpty()) {
- int v = dequeue();
- if (graph.get(v) != null)
- add_All(graph.get(v));
- System.out.print(v + " ");
- }
- }
- public static void add_All(LinkedList < Integer > directly_connected) {
- for (int v: directly_connected) {
- if (!visited.contains(v)) {
- enque(v);
- visited.addLast(v);
- }
- }
- }
- public static void enque(int v) {
- queue.addLast(v);
- }
- public static int dequeue() {
- return queue.removeFirst();
- }
- public static void build_graph() {
- LinkedList l = new LinkedList();
- l.add(2);
- l.add(3);
- l.add(4);
- graph.put(1, l);
- l = new LinkedList();
- l.add(5);
- l.add(6);
- l.add(7);
- l.add(1);
- graph.put(2, l);
- l = new LinkedList();
- l.add(8);
- l.add(1);
- graph.put(3, l);
- l = new LinkedList();
- l.add(9);
- l.add(10);
- l.add(1);
- graph.put(4, l);
- l = new LinkedList();
- l.add(2);
- graph.put(5, l);
- graph.put(6, l);
- graph.put(7, l);
- l = new LinkedList();
- l.add(3);
- graph.put(8, l);
- l = new LinkedList();
- l.add(4);
- graph.put(9, l);
- graph.put(10, l);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment