How are a graph and a binary tree represented as data structures in CLRS' Introduction to Algorithms?

Question

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.

Binary trees

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?

Thanks.

---

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[1], A[2], ..., 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.

Answer 1

Does G.Adj being an array means that the vertices being its indices must be natural numbers 1, 2, ...?

Either a natural number or an object that can be mapped to natural number between $1$ and $n$. You don't need this fine grained distinction to discuss the pseudocode of the algorithm since you can go form one to another (e.g., by storing an integer ID of each node in the node object, and by keeping an array that maps IDs back to objects).

Is G.V an array that stores the vertices of G?

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?

G.V can be an array that stores the vertices, our you could simply iterate over all vertices IDs of the graph (i.e., for i=1,...,n:).

Again, u could be an object with color, pi, etc as fields or these information can be maintained as satellite data somewhere else, for example, with parallel arrays indexed with the vertex ID. The important bit is that, given a vertex u, you can access its satellite information.

There is no absolute "better" solution. It probably depends to your specific case.

Does T have an attribute T.V for storing the representations of its nodes? Similar to G.V for a graph?

It could, but it doesn't have to.

Are the representations of the nodes of a binary tree stored in an array?

Again, they could but they don't have to. You could allocate an instance of each node object independently in the heap and refer to nodes with pointers. This is what the quoted part of the book appears to be describing.

Alternatively, you could allocate all nodes in the tree contiguously into a single array. You can still use pointers to refer to other nodes, or you could replace pointers with the index in this backing array (a pointer and the index are essentially the same thing in this case).

Answer 2

Figure 22.1 in the CLRS textbook seems to imply that the adjacency list of a graph is stored as follows: the nodes are labelled $0,1,\ldots,n-1$, there is an array of $n$ pointers, and each pointer points to a linked list of all neighbors of the corresponding node.

For example, one can create an array of $n$ pointers and initialize them to NIL. Each time a new edge $ji$ is added (to the initially empty graph), element $i$ is added to the $j$th linked list and $j$ is added to the $i$th linked list (in the case of undirected graphs).

You could take the approach of creating an object for each vertex or edge, as you suggest. This is done in [Guttag, “Introduction to Computation and Programming Using Python, 2nd Edition”, Section 12.2].

Or, you could create a list of lists in Python, of the form $[Adj[0], Adj[1],…,Adj[n-1]]$, where $Adj[1] = [2,3,7]$ would mean vertices $2,3,7$ are neighbors of $1$. The for loops would just iterate over this list, as desired. You could use an array d, where d[i] is the distance to node i, i.e. the d-value of node i.

Another implementation for graphs - this one is in C - can be found in [Steven Skiena, “The Algorithm Design manual”, Section 5.5].

For binary search trees, the tree is completely determined once you know the pointer variable T, which points to the root node of the tree. By following the left child or right child pointers of each node, one can reach any node in the entire tree.

Another good reference is [Aho, Hopcroft and Ullman, “Data Structures and Algorithms”]. Their section on linked lists is a good starting point if you want to understand pointers. They also explain how binary trees can be implemented with arrays (and apply this to Huffman codes).