arpit728

DFS

Dec 24th, 2015
266
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Arrays;
  2. import java.util.Iterator;
  3. import java.util.LinkedList;
  4. import java.util.Scanner;
  5. import java.util.Stack;
  6.  
  7. public class DepthFirstSearch {
  8.  
  9. public static void main(String[] args) {
  10. Scanner sc=new Scanner(System.in);
  11.  
  12. System.out.print("Hey, enter the no. of vertices in your graph : ");
  13. int n=sc.nextInt();
  14. LinkedList<Vertex1>[]list=new LinkedList[n];
  15. Stack<Integer> stack=new Stack<Integer>();
  16. int start;
  17. int output[]=new int[n];
  18. int i=0;
  19. LinkedList<Vertex1> vertex1List =new LinkedList<Vertex1>();
  20.  
  21. for (int j = 0; j < n; j++) {
  22. vertex1List.add(new Vertex1(0, j));
  23. }
  24.  
  25. for (i = 0; i <n; i++) {
  26. list[i]=new LinkedList<Vertex1>();
  27.  
  28. System.out.print("\nEnter the no. of vertices adjacent to vertex "+i+" ");
  29. int temp=sc.nextInt();
  30. System.out.print("Enter the vertices that are adjacent to vertex "+i+" : ");
  31. for(int j=0;j<temp;j++){
  32. list[i].add(vertex1List.get(sc.nextInt()));
  33. }
  34. System.out.println(list[i]);
  35.  
  36. }
  37. System.out.println("\nEnter the starting point : ");
  38. start=sc.nextInt();
  39. vertex1List.get(start).setColor(1);
  40. stack.push(start);
  41. int flag=0;
  42. i=1;
  43. output[0]=start;
  44.  
  45. while(!stack.isEmpty()){
  46. Iterator itr=list[stack.peek()].iterator();
  47. flag=0;
  48. while (itr.hasNext()) {
  49.  
  50. Vertex1 v=(Vertex1) itr.next();
  51. if(v.color==0){
  52. flag=1;
  53. v.setColor(1);
  54. stack.push(v.val);
  55. output[i]=v.val;
  56. i++;
  57. break;
  58. }
  59. }
  60. if (flag==0) {
  61. Vertex1 v= vertex1List.get(stack.pop());
  62. v.color=2;
  63. }
  64.  
  65. }
  66. System.out.println(Arrays.toString(output));
  67.  
  68. }
  69.  
  70. }
  71. class Vertex1 {
  72. int color,val;
  73.  
  74. public Vertex1(int color, int val) {
  75. super();
  76. this.color = color;
  77. this.val = val;
  78. }
  79.  
  80. public int getColor() {
  81. return color;
  82. }
  83.  
  84. public void setColor(int color) {
  85. this.color = color;
  86. }
  87.  
  88. public int getVal() {
  89. return val;
  90. }
  91.  
  92. public void setVal(int val) {
  93. this.val = val;
  94. }
  95.  
  96. @Override
  97. public String toString() {
  98. return "Vertex1 [color=" + color + ", val=" + val + "]";
  99. }
  100. }
RAW Paste Data