# Two kind bfs [hard deletion and soft deletion]

• 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) {
}
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) {
}
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;
}``````

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