BFS-DFS-DEMO/DFS at master · LuisRobaina/BFS-DFS-DEMO · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.awt.Color;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

class DFS {
ArrayList<Node> nodes;
    // Visiting Queue
    Stack<Node> visit;
    // Map set to backtrace
    HashMap<Node, Node> backtrace;
    // Set of visited
    ArrayList<Node> visited;

    DFS(ArrayList<Node> nodes) {
        visit = new LinkedList<>();
        visited = new ArrayList<>();
        this.nodes = nodes;
        traverse(nodes.get(0), false, null, null);
    }
    DFS(ArrayList<Node> nodes, Node source, Node sink) {
        backtrace = new HashMap<Node, Node>();
        visit = new LinkedList<>();
        visited = new ArrayList<>();
        this.nodes = nodes;
        traverse(source, true, source, sink);
    }

    private void traverse(Node n, boolean path, Node source, Node sink) {
        visit.push(n);
        visited.add(n);
        StdDraw.filledCircle(n.x, n.y, 0.005);
        explore(n,source,sink);
        visit.pop();
        System.out.println("DONE");
    }

    private void explore(Node n, Node source, Node sink) {
        for(Node a : n.bag){
            StdDraw.setPenColor(Color.RED);
            if(!visited.contains(a)){
                StdDraw.line(n.x, n.y, a.x, a.y);
                visited.add(a);
                visit.push(a);
                visited.add(a);
                StdDraw.pause(1500);
                StdDraw.setPenColor(Color.BLACK);
                StdDraw.line(n.x, n.y, a.x, a.y);
                explore(a,source,sink);
            }
        }
        visit.pop();
    }
    private void explore(Node n) {
        for(Node a : n.bag){
            StdDraw.setPenColor(Color.RED);
            if(!visited.contains(a)){
                StdDraw.line(n.x, n.y, a.x, a.y);
                visited.add(a);
                visit.push(a);
                visited.add(a);
                StdDraw.pause(1500);
                StdDraw.setPenColor(Color.BLACK);
                StdDraw.line(n.x, n.y, a.x, a.y);
                explore(a,source,sink);
            }
        }
        visit.pop();

    }

}