LeetCode/Graph 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
package BFS;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Graph {
    private int vertex;
    private LinkedList<Integer>[] neighbors;
    // use this to represent neighbour , not good , may use HaspMap<key, value>
    // HashMap<Integer, LinkedList<Integer>>

    public Graph(int vertex) {
        this.vertex = vertex;
        neighbors = new LinkedList[vertex];

        for (int i = 0; i < vertex; i++) {
            neighbors[i] = new LinkedList<>();
        }
    }

    //un directional edge,
    void addEdge(int v, int w) {
        neighbors[v].add(w);
    }

    void BFS(int startVertex) {

        // Hashmap to give visited
        HashMap<Integer, Boolean> visitedVertex = new HashMap<>();

        Queue<Integer> queue = new LinkedList<>();
        queue.add(startVertex);
        visitedVertex.put(startVertex, true);

        while (!queue.isEmpty()) {
            int top = queue.poll();

            System.out.println("current vertex " + top);
            LinkedList<Integer> neighbours = neighbors[top];

            for (int current : neighbours) {

                if (!visitedVertex.containsKey(current)) {
                    queue.add(current);
                    visitedVertex.put(current,true);
                }
            }
        }

    }

    public static void main(String[] args) {
        Graph g1 = new Graph(4);
        g1.addEdge(0,1);
        g1.addEdge(1,0);
        g1.addEdge(1,2);
        g1.addEdge(1,3);
        g1.addEdge(2,1);
        g1.addEdge(2,3);
        g1.addEdge(3,1);
        g1.addEdge(3,2);
       // g1.BFS(0);

        Graph g2 = new Graph(6);
        g2.addEdge(0,1);
        g2.addEdge(0,2);
        g2.addEdge(1,0);
        g2.addEdge(1,3);
        g2.addEdge(1,4);
        g2.addEdge(2,0);
        g2.addEdge(2,4);
        g2.addEdge(3,1);
        g2.addEdge(3,4);
        g2.addEdge(3,5);
        g2.addEdge(4,1);
        g2.addEdge(4,2);
        g2.addEdge(4,3);
        g2.addEdge(4,5);
        g2.addEdge(5,3);
        g2.addEdge(5,4);

        g2.BFS(0);


    }
}