document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. package GraphAlgorithms.DFS;
  2.  
  3. /**
  4.  * Created by Anuradha Sanjeewa on 23/12/2015.
  5.  */
  6.  
  7. import java.util.*;
  8.  
  9. public class Graph {
  10.     private HashMap<Integer, Node> nodes;
  11.     private int count;
  12.  
  13.     public Graph(int vCount) {
  14.         nodes = new HashMap<>();
  15.         count = vCount;
  16.         for (int i = 0; i < vCount; i++) {
  17.             nodes.put(i, new Node(i));
  18.         }
  19.     }
  20.  
  21.     public int getCount() {
  22.         return count;
  23.     }
  24.  
  25.     public void addEdge(int id, int end) {
  26.         nodes.get(id).addNeighbour(nodes.get(end));
  27.     }
  28.  
  29.     public void runDFS(int vertex) {
  30.         Stack<Node> stack = new Stack<>();
  31.         HashMap<Integer, Node> visited = new HashMap<>();
  32.         Node u;
  33.         stack.push(nodes.get(vertex));
  34.         while (stack.size() > 0) {
  35.             u = stack.pop();
  36.             if (!visited.containsKey(u.getId())) {
  37.                 visited.put(u.getId(), u);
  38.                 System.out.println("Discovering node: " + u.getId());
  39.                 u.getNeighbours().forEach(stack::push);
  40.             }
  41.         }
  42.     }
  43. }
  44.  
  45. class Node {
  46.     private int id;
  47.     private ArrayList<Node> neighbours;
  48.  
  49.     public Node(int id) {
  50.         neighbours = new ArrayList<>();
  51.         this.id = id;
  52.     }
  53.  
  54.     public void addNeighbour(Node n) {
  55.         this.neighbours.add(n);
  56.     }
  57.  
  58.     public ArrayList<Node> getNeighbours() {
  59.         return this.neighbours;
  60.     }
  61.  
  62.     public int getId() {
  63.         return id;
  64.     }
  65. }
');