Java BFS - Equivalent to Finding Connected Components in a Graph


  • 5
    public int findCircleNum(int[][] M) {
        int count = 0;
        for (int i=0; i<M.length; i++)
            if (M[i][i] == 1) { count++; BFS(i, M); }
        return count;
    }
    
    public void BFS(int student, int[][] M) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(student);
        while (queue.size() > 0) {
            int queueSize = queue.size();
            for (int i=0;i<queueSize;i++) {
                int j = queue.poll();
                M[j][j] = 2; // marks as visited
                for (int k=0;k<M[0].length;k++) 
                    if (M[j][k] == 1 && M[k][k] == 1) queue.add(k);
            }
        }
    }
    

  • 0
    H

    @compton_scatter how about this case:

    1 0 1
    0 1 0
    1 0 1

    maybe your solution is correct, but it is not same as number of connected components


  • 0
    A
    This post is deleted!

  • 0
    S
     while (queue.size() > 0) {
            int queueSize = queue.size();
            for (int i=0;i<queueSize;i++) {
    

    The inner loop is unnecessary. Think of how the queue is buffered in your algorithm. :)


  • 0
    A

    @compton_scatter
    we can change
    for (int k=0;k<M[0].length;k++)
    to
    for (int k=student;k<M[0].length;k++)

    no need to start from 0, can start from 'student'.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.