# Clean Java Solutions: BFS and DFS

• 1. BFS

Refers to classic Kahn's Algorithm.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {

// build the directed graph with adjacency list
Map<Integer, Set<Integer>> outgoing = new HashMap<>();  // node ---> set of nodes
Map<Integer, Set<Integer>> incoming = new HashMap<>();  // node <--- set of nodes
for (int i = 0; i < numCourses; i++) {
outgoing.put(i, new HashSet<>());
incoming.put(i, new HashSet<>());
}
for (int i = 0; i < prerequisites.length; i++) {
}

/**
* Kahn's Algorithm (BFS)
*/

// add all nodes with no imcoming edge to the queue
for (int i = 0; i < numCourses; i++) {
if (incoming.get(i).isEmpty()) {
queue.offer(i);
}
}

while (!queue.isEmpty()) {
int course = queue.poll();
for (int neighbor : outgoing.get(course)) {
// edge: course ---> neighbor
incoming.get(neighbor).remove(course);
if (incoming.get(neighbor).isEmpty()) {
queue.offer(neighbor);
}
}
}

// if graph has edges, there is no topological ordering exists, return false
for (int i = 0; i < numCourses; i++) {
if (!incoming.get(i).isEmpty()) {
return false;
}
}

return true;
}
}
``````

2. DFS

Use a `visited[]` array:

• `visited[i] == 0` represents the course `i` has NOT been visited;
• `visited[i] == 1` represents the course `i` is being visited;
• `visited[i] == 2` represents the course `i` has been visited.

The implementation is pretty straightforward.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {

// build the directed graph with adjacency list
Map<Integer, Set<Integer>> adjacencyList = new HashMap<>();  // node ---> set of nodes
for (int i = 0; i < numCourses; i++) {
}
for (int i = 0; i < prerequisites.length; i++) {
}

/**
* Find Circle (DFS)
*/

int[] visited = new int[numCourses];  // 0: unvisited; 1: being visited; 2: visited
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0 && !dfs(i, adjacencyList, visited)) {
return false;
}
}

return true;
}

// detect circle (if a circle is detected, return false)
private boolean dfs(int course, Map<Integer, Set<Integer>> adjacencyList, int[] visited) {

visited[course] = 1;  // mark course as being visited
for (int neighbor : adjacencyList.get(course)) {
if (visited[neighbor] == 1) {  // circle detected
return false;
}
if (visited[neighbor] == 0 && !dfs(neighbor, adjacencyList, visited)) {  // circle detected
return false;
}
}
visited[course] = 2;  // mark course as visited
return true;
}
}
``````

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