In CLRS' Introduction to Algorithms:
(1) In 22.1 Representations of graphs
The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V. For each u in V , the adjacency list Adj[u] contains all the vertices v such that there is an edge (u,v) in E. That is, Adj[u] consists of all the vertices adjacent to u in G. (Alternatively, it may contain pointers to these vertices.) Since the adjacency lists represent the edges of a graph, in pseudocode we treat the array Adj as an attribute of the graph, just as we treat the edge set E. In pseudocode, therefore, we will see notation such G.Adj[u].
Does G.Adj being an array means that the vertices being its indices must be natural numbers 1, 2, ...?
(2) In 22.3 Depth-first search
DFS(G) 1 for each vertex u in G.V 2 u.color = WHITE 3 u.pi = NIL 4 time = 0 5 for each vertex u in G.V 6 if u.color == WHITE 7 DFS-VISIT(G,u) DFS-VISIT(G,u) 1 time = time + 1 // white vertex u has just been discovered 2 u.d = time 3 u.color = GRAY 4 for each v in G.Adj[u] // explore edge (u,v) 5 if v.color == WHITE 6 v. = u 7 DFS-VISIT(G,v) 8 u.color = BLACK // blacken u; it is finished 9 time = time + 1 10 u.f = time
Is G.V an array that stores the vertices of G?
u is an element in G.V, and is used as an index to access an element in array G.Adj. Does u having attribute color, pi, d and f means that u is an object?
So is u a natural number or an object?
Which is better in representing a vertex, as a natural number or an object?
Which is better,
representing vertices as objects with names and stored independently, and referring to each vertex object by its name, or
representing vertices as objects stored together as elements in an array, and referring to vertex objects as elements of the array?
(3) In 10.4 Representing rooted trees:
In this section, we look specifically at the problem of representing rooted trees by linked data structures. We first look at binary trees, and then we present a method for rooted trees in which nodes can have an arbitrary number of children.
We represent each node of a tree by an object. As with linked lists, we assume that each node contains a key attribute. The remaining attributes of interest are pointers to other nodes, and they vary according to the type of tree.
Figure 10.9 shows how we use the attributes p, left, and right to store pointers to the parent, left child, and right child of each node in a binary tree T. If x.p = NIL, then x is the root. If node x has no left child, then x.left = NIL, and similarly for the right child. The root of the entire tree T is pointed to by the attribute T.root. If T.root = NIL, then the tree is empty.
So a binary tree is represented as an object T, and a node of the binary tree as an object T.x in the pseudolanguage.
How different are object T for a binary tree and object G for a graph?
Does T have an attribute T.V for storing the representations of its nodes? Similar to G.V for a graph?
Are the representations of the nodes of a binary tree stored in an array?
p.s. the pseudolanguage used in the book is described in 2.1 Insertion sort:
We access array elements by specifying the array name followed by the index in square brackets. For example, A[i] indicates the ith element of the array A. The notation ".." is used to indicate a range of values within an array. Thus, A[1 .. j] indicates the subarray of A consisting of the j elements A, A, ..., A[j].
We typically organize compound data into objects, which are composed of attributes. We access a particular attribute using the syntax found in many object-oriented programming languages: the object name, followed by a dot, followed by the attribute name. For example, we treat an array as an object with the attribute length indicating how many elements it contains. To specify the number of elements in an array A, we write A.length.
We treat a variable representing an array or object as a pointer to the data representing the array or object. For all attributes f of an object x, setting y = x causes y.f to equal x.f . Moreover, if we now set x.f = 3, then afterward not only does x.f equal 3, but y.f equals 3 as well. In other words, x and y point to the same object after the assignment y = x.
Our attribute notation can cascade. For example, suppose that the attribute f is itself a pointer to some type of object that has an attribute g. Then the notation x.f.g is implicitly parenthesized as (x.f).g. In other words, if we had assigned y = x.f , then x.f.g is the same as y.g.
Sometimes, a pointer will refer to no object at all. In this case, we give it the special value NIL.