# #Java #BFS #Topological-sorting

• This is a typical BFS topological sorting answer. Other than the algorithm, I'm much more interested in the Java representation of a graph. Should we use a `int[][]`/`boolean[][]`, `List<Set<Integer>>`, `Set<Integer>[]` to represent a graph?

• `int[][]`/`boolean[][]` is a workable idea, but it wastes some memory
• `List<Set<Integer>>` or `List<List<Integer>>` seems to be a good alternative, but it's painful to check the validity of the index every time.
• `Set<Integer>[]` is a nice workaround as long as we remember it's not allowed to put the parameterized type in the array constructor.

#### boolean[][] graph

``````    public boolean canFinish(int numCourses, int[][] prerequisites) {
boolean[][] graph = new boolean[numCourses][numCourses];
int[] indegree = new int[numCourses];

// make a graph && indegree array
for(int r=0; r<prerequisites.length; ++r) {
int nextV = prerequisites[r][0];
int v = prerequisites[r][1];
graph[v][nextV] = true;
indegree[nextV]++;
}

ArrayDeque<Integer> queue = new ArrayDeque<>();
for(int i=0; i<indegree.length; i++) {
if(indegree[i] == 0) queue.offer(i);
}

if (queue.isEmpty()) return false;
int count = 0;

while(!queue.isEmpty()) {
count ++;
Integer v = queue.poll();
indegree[v] = -1;
for(int nextV=0; nextV<numCourses; ++nextV) {
if (graph[v][nextV]) {
if (indegree[nextV] == -1) return false;
indegree[nextV]--;
if (indegree[nextV] == 0) queue.offer(nextV);
}
}
}
return count == numCourses;
}
``````

#### Set<Integer>[]

``````    public boolean canFinish(int numCourses, int[][] prerequisites) {
Set<Integer>[] graph = new Set[numCourses];
int[] indegree = new int[numCourses];

// make a graph && indegree array
for(int r=0; r<prerequisites.length; ++r) {
int nextV = prerequisites[r][0];
int v = prerequisites[r][1];
if (graph[v] == null) graph[v] = new HashSet<>();
indegree[nextV]++;
}

ArrayDeque<Integer> queue = new ArrayDeque<>();
for(int i=0; i<indegree.length; i++) {
if(indegree[i] == 0) queue.offer(i);
}

if (queue.isEmpty()) return false;
int count = 0;

while(!queue.isEmpty()) {
count ++;
Integer v = queue.poll();
indegree[v] = -1;

if (graph[v] != null) {
for (int nextV : graph[v]) {
if (--indegree[nextV] == 0) queue.offer(nextV);
}
}
}
return count == numCourses;
}
``````

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