I am learning algorithms and data structures from this awesome resource Algorithms. Rather than doing dry reading I am trying to re-write all the code myself so that I can learn coding as well as design decisions at the same time(like: what APIs to expose and how to do assertions etc.) so, below is my simplified code which is mostly copied from this version.
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Queue;
public class CC {
private int count;
private boolean[] marked;
private int[] id;
public CC(Graph G) {
marked = new boolean[G.V()];
id = new int[G.V()];
count = 0;
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
dfs(G, v);
count++;
}
}
}
public int count() {
return count;
}
public int id(int v) {
return id[v];
}
private void dfs(Graph G, int u) {
if (!marked[u]) {
marked[u] = true;
id[u] = count;
for(int v : G.adj(u)) {
dfs(G, v);
}
}
}
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
CC cc = new CC(G);
// number of connected components.
int M = cc.count();
StdOut.println(M + " components");
// Get number of vertices in each component.
Queue<Integer>[] components = (Queue<Integer>[]) new Queue[M];
for (int i = 0; i < M; i++) {
components[i] = new Queue<Integer>();
}
for (int v = 0; v < G.V(); v++) {
components[cc.id(v)].enqueue(v);
}
for (int i = 0; i < M; i++) {
for (int v : components[i]) {
StdOut.print(v + " ");
}
StdOut.println();
}
}
}
I am writing up some of the doubts I have and understanding them can let me write better code in future and understand the authors intent better(there might be some stupid question so please bear with me :p ):
- Instance variable
G
, why its always declared with capital? - Can I do
final Graph G
to make sure its never reassigned anywhere? - Why
Queue
and not simpleArrayList
?(while printing all the vertices in the component). - Public interfaces with names like
V
, I am always taught to write descriptive names. In what conditions these names are allowed? - Why we need abstractions like
StdOut
when we already have library support likeSystem.out
?