Choice of variable names and types in graph algorithm

Question

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 ):

1. Instance variable G, why its always declared with capital?
2. Can I do final Graph G to make sure its never reassigned anywhere?
3. Why Queue and not simple ArrayList?(while printing all the vertices in the component).
4. Public interfaces with names like V, I am always taught to write descriptive names. In what conditions these names are allowed?
5. Why we need abstractions like StdOut when we already have library support like System.out?

Answer 1

You asked

Instance variable G, why its always declared with capital?

and

Public interfaces with names like V, I am always taught to write descriptive names. In what conditions these names are allowed?

I guess these two things have the same reason: the original algorithm description and the related sections in your text book has the form of a mathematical text. Mathmaticians often use one letters for variables, and capital letters for sets and set structures like graphs, so it is no surprise the one who implemented the algorithm just stuck to that convention. For such an algorithmic context this is ok, since you want to use the similar terms and abbreviations in your code as the ones used in your text book.

Can I do final Graph G to make sure its never reassigned anywhere?

Yes, you can. However, since G is only used as a local variable in more or less short functions, this does not add much value to the code, only additional "noise". See this SO post, read the two topmost answers, one is saying "yes, do it", and the other one "it is a waste of time". In your example above, I tend to the agree more to the second answer.

Why Queue and not simple ArrayList?(while printing all the vertices in the component)

Actually, it does not matter - using an ArrayList in the shown piece of code would neither simplify nor complicate the code. It seems just to be a matter of taste. From the way you asked you seem to be biased, thinking an ArrayList seem to be "more simple" than a Queue, but ask yourself why you think this and how the code will change when you replace one type by the other.

Why we need abstractions like StdOut when we already have library support like System.out

If you look into the initial comment section of the original Java class StdOut: it is described there precisely. The differences are related to the character set, float/double number formatting and flushing. Moreover, the earlier editions of the "Algorithms" book were not written using Java, but older languages like Pascal, C and C++, so providing an abstraction for standard output makes the book more language agnostic.