Storing Graphs in Computer Memory
Larry E. Thomas · Mathematical Association of America eBooks · 2009
Introduction Many of the structures we use in discrete mathematics are nonlinear when they are drawn in the usual way on paper. For example, a graph will often have many edges leaving or entering a given vertex, with the number of edges changing from vertex to vertex. Drawing such a graph on paper could produce a rather messy diagram which takes two dimensions to represent. However, most graph algorithms used in problems of any size are executed on a computer which has only a linear (one-dimensional) memory. The question naturally arises: How do we represent an inherently two-dimensional object, such as a graph or a matrix, in one dimension? This note explores some of the ways this question can be answered. A computer's memory We will begin with a simplified explanation of the way the memory of a regular desktop computer might be organized. The memory consists of consecutive locations where data, represented in a binary code, can be stored. In a memory with n consecutive locations, the locations are numbered with addresses beginning with address 0: 0, 1, 2, …, n . If, for example, a single location can hold one byte (eight bits) of binary code, a one-kilobyte memory will have locations numbered 0, 1, 2, …, 1024, since 1Kb of memory contains 2 10 = 1024 bytes. Pictorially, we can think of the memory as a long collection of numbered boxes as seen in Figure 1.