Two kind bfs [hard deletion and soft deletion]


  • 0
    F

    Principle:
    // (1)if there only are n different node entering into queue, then there must be n-1 different
    // edges exist in graph, (2)this must be tree not graph.
    // if it is a tree, you can get the (1), so (1) <=> (2)
    Hard Deletion

    public boolean validTreeBfsHardDelete(int n, int[][] edges) {
             Set<Integer>[] neigbors = new Set[n];
             for (int i = 0; i < n; i++) neigbors[i] = new HashSet<Integer>();
             for (int[] edge: edges) {
                 neigbors[edge[0]].add(edge[1]);
                 neigbors[edge[1]].add(edge[0]);
             }
             Queue<Integer> queue = new LinkedList<>();
             queue.add(0);
             int count = 0;
             boolean[] visited = new boolean[n];
             while (!queue.isEmpty()) {
                 int cur = queue.poll();
                 if (visited[cur]) return false;
                 visited[cur] = true;
                 count++;
                 // if there is a cycle then same node will be entered twice in the queue
                 for (int neighbor: neigbors[cur]) {
                     queue.offer(neighbor);
                     // hard delete
                     neigbors[neighbor].remove(cur);
                 }
             }
             return count == n;
         }
    

    Soft Deletion

    public boolean validTreeBfs(int n, int[][] edges) {
             List<Integer>[] neigbors = new List[n];
             for (int i = 0; i < n; i++) neigbors[i] = new ArrayList<Integer>();
             for (int[] edge: edges) {
                 neigbors[edge[0]].add(edge[1]);
                 neigbors[edge[1]].add(edge[0]);
             }
             Queue<Integer> queue = new LinkedList<>();
             queue.add(0);
             int count = 0;
             boolean[] visited = new boolean[n];
             while (!queue.isEmpty()) {
                 int cur = queue.poll();
                 if (visited[cur]) return false;
                 visited[cur] = true;
                 count++;
                 // if there is a cycle then same node will be entered twice in the queue
                 for (int neighbor: neigbors[cur]) {
                     // soft delete.
                     if (!visited[neighbor])queue.offer(neighbor);
                 }
             }
             return count == n;
         }

Log in to reply
 

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