Java Graph Theory using DFS (detailed explanation)


  • 1
    L

    The key to solving this problem is to recognize that if A,B,C and D are friends, they all will show up in the set of visited nodes after I finish a visit from A to all of his friends. That brings us to an algorithm where I do visit from each node to all of his friends. Before we start visiting, we could see if it is part of the set of all visited nodes so far. If it isn't then a new friend circle should be formed which this new person (who is now being visited ) is a part of. An example:

     A->B, B->C,  D
    

    Traverse A. Look for A in the set of visited nodes. Since we don't find it, we have created 1 circle. Once you finish traversing A, the set should contain A and B in it. Now, traverse B. Since B exists in the visited set, it will be a part of the same old circle from A. Do traverse B and add C to the set of visited nodes. Same story with C. D will not be found inside the set to it creates a new circle where only D belongs.

        public int findCircleNum(int[][] M) {
            List<List<Integer>> people = new ArrayList<>(M.length);
            for(int i=0;i<M.length;i++) {
                people.add(new ArrayList<>());
                for(int j=0;j<M.length;j++) {
                    if(M[i][j]==1) {
                        people.get(i).add(j);
                    }
                }
            }
            
            Stack<Integer> stack = new Stack<>();
            Set<Integer> visited = new HashSet<>();
            int count=0;
            for(int i =0;i<people.size();i++) {
                //new circle if it doesn't exist in the set of visited friends.
                if(!visited.contains(i)) {
                    count++;
                }
                
                stack.push(i);
                visited.add(i);
                while(!stack.isEmpty()) {
                    int val = stack.pop();
                    for(int f : people.get(val)) {
                        if(!visited.contains(f)) {
                            stack.push(f);
                            visited.add(f);
                        }
                    }
                }
            }
            return count;
        }
    

Log in to reply
 

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