BFS-DFS-DEMO/DFS.java 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
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 Stack();
        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 Stack();
        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);
        if (path)
            explore(n, source, sink);
        else
            explore(n);

        System.out.println("DONE");
    }

    int color = 0;

    private void explore(Node n, Node source, Node sink) {
        for (Node a : n.bag) {
            if (a == sink) {
                backtrace.put(a, n);
                switch (color) {
                case 0:
                    StdDraw.setPenColor(Color.BLUE);
                    break;
                case 1:
                    StdDraw.setPenColor(Color.ORANGE);
                    break;
                case 2:
                    StdDraw.setPenColor(Color.darkGray);
                    break;
                case 3:
                    StdDraw.setPenColor(Color.green);
                    break;
                default:
                    StdDraw.setPenColor(Color.magenta);
                }
                while (a != source) {
                    Node priv = backtrace.get(a);
                    StdDraw.line(a.x, a.y, priv.x, priv.y);
                    a = priv;
                }
                color++;
            }

            StdDraw.setPenColor(Color.RED);
            if (!visited.contains(a)) {
                StdDraw.line(n.x, n.y, a.x, a.y);
                visited.add(a);
                visit.push(a);
                backtrace.put(a, n);
                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);
            }
        }
        visit.pop();
    }

}