LeetCode/GraphBFS at master · XinCai/LeetCode · 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
package DFS;


import java.util.*;

public class BFSDemo {
    /**
     *        Graph
     *
     *         0
     *        / \
     *       1 - 2
     *      /     \
     *     4      3
     *      \    /
     *        5
     *
     *
     */

    public static void main(String[] args) {
        Node<Integer> node_0 = new Node<>();
        node_0.value = 0;

        Node<Integer> node_1 = new Node<>();
        node_1.value = 1;

        Node<Integer> node_2 = new Node<>();
        node_2.value = 2;

        Node<Integer> node_3 = new Node<>();
        node_3.value = 3;

        Node<Integer> node_4 = new Node<>();
        node_4.value = 4;

        Node<Integer> node_5 = new Node<>();
        node_5.value = 5;

        List<Node<Integer>> neighbours_0 = new ArrayList<>();
        neighbours_0.add(node_1);
        neighbours_0.add(node_2);
        node_0.neighbours = neighbours_0;

        List<Node<Integer>> neighbours_1 = new ArrayList<>();
        neighbours_1.add(node_0);
        neighbours_1.add(node_2);
        neighbours_1.add(node_4);
        node_1.neighbours = neighbours_1;

        List<Node<Integer>> neighbours_2 = new ArrayList<>();
        neighbours_2.add(node_0);
        neighbours_2.add(node_1);
        neighbours_2.add(node_3);
        node_2.neighbours = neighbours_2;

        List<Node<Integer>> neighbours_3 = new ArrayList<>();
        neighbours_3.add(node_2);
        neighbours_3.add(node_5);
        node_3.neighbours = neighbours_3;

        List<Node<Integer>> neighbours_4 = new ArrayList<>();
        neighbours_4.add(node_1);
        neighbours_4.add(node_5);
        node_4.neighbours = neighbours_4;

        List<Node<Integer>> neighbours_5 = new ArrayList<>();
        neighbours_5.add(node_4);
        neighbours_5.add(node_3);
        node_5.neighbours=neighbours_5;

        BFSDemo bfsDemo = new BFSDemo();
        bfsDemo.BFS(node_5);
    }

    private void BFS(Node startNode){
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> visitedNode = new HashSet<>();  // !!! ==== Use HashSet to check visited nodes ====!!!!!!
        queue.add(startNode);
        visitedNode.add(startNode);

        while (!queue.isEmpty()){
            Node top = queue.poll();
            System.out.println("Grapah BFS visited: " + top.value );
            List<Node> neighbours = top.neighbours;
            for (Node current : neighbours) {
                if (!visitedNode.contains(current)){
                    visitedNode.add(current);
                    queue.add(current);
                }
            }
        }
    }
}