Discrete Math: Array-Pointer Representation

Question

I am confused as to how the table is filled in for a pointer-array representation of a graph, and I can't find anything online that talks much about array-pointer representation. My book does not clearly explain why the numbers are placed where and overall I just feel lost where these numbers even came from. Can anyone explain to me how to fill a table out?

Here is the books example and array-pointer representation:

I know the number 11 comes from the total number of edges and nodes, I think. The book mentions something about indexes but I don't understand where these indexes come from in the graph..?

Answer 1

The first $5$ rows correspond to the five nodes: row $k$ corresponds to node $k$. Each of those rows is the head of a linked list of rows corresponding to the edges leaving that node. The remaining rows correspond to the edges. To see how that works, let’s take a look at nodes $1$ and $2$.

The only edge leaving node $1$ is the edge of weight $2$ going to node $3$. We enter that edge in the first available row, which is row $6$, and set the row $1$ pointer to point to row $6$. In row $6$ the Node field is set to $3$, the node to which the edge points, the Weight field is filled with the weight of the edge, and the Pointer field is set to point to the next edge leaving node $1$. There is no such edge, so fill the Pointer field with $0$, indicating the end of this linked list.

There are two edges leaving node $2$: one goes to node $1$, the other to node $4$. We enter them in the order of their targets, so we deal first with the edge of weight $4$ from node $2$ to node $1$, entering it in row $7$, the first available row. It points to node $1$, so we enter $1$ in the Node field, and we enter it’s weight of $4$ in the Weight field. This time there is another edge leaving the node that we’re processing, so we chain to it: we fill the Pointer field with the number of the row in which that edge is entered. It isn’t actually entered yet, so it will go in the first available row, which is row $8$. It points to node $4$ and has weight $2$, so the first two entries in row $8$ are $4$ and $2$, respectively. There are no more edges leaving node $2$, so the last entry in the row is $0$, marking the end of the linked list of edges leaving node $2$.

From here you should be able to verify the remaining entries in the table.

Answer 2

This is nothing but an adjacency list representation of a directed graph without using pointers. The first 5 entries in the table are the heads of the linked lists of the 5 nodes, each of which contains all the nodes (and their weights) adjacent to those nodes.

For example, consider table row in line 2 (that's the index the book talks about). The pointer field in that row is 7, which is the start of the list of out-edges from node 2.

Going to row 7, we have node = 1, weight = 4. That means that node 2 has an out-edge to node 1 with weight 4. You can see from the picture of the graph that that's correct. The row 7 pointer field is 8, meaning that there's another out-edge from node 2 yet to come.

We go to row 8, as directed and find that node 2 has another out-edge to node 4 and that edge has weight 2, again as expected from the picture. The row 8 pointer field is 0, meaning that there are no further edges from node 2.

In complete detail for your digraph we have $$\begin{array}{c|cc} \mathbf{Node} & \mathbf{adjacent} & \mathbf{adjacent}\\ 1 & 3 & \\ 2 & 1 & 4 \\ 3 & 2 & \\ 4 & & \\ 5 & 2 \end{array}$$