There is no unique answer to the implementation of graphs in computers. On the one hand it is possible to imagine many models apriori but, on the other hand, the implementation of a graph depends on the way in which it will be used. The choice of a model may have a direct influence on the efficiency of the algorithm in terms of complexity. In order to classify the various computer models of graphs, the three following principles can be distinguished:

1. Give the possibility of finding out if two given vertices are neighbors, that is joined by an edge in the graph. Furthermore, in the case of a non-simple graph, give the number of edges joining the vertices under consideration. The natural way to do this for a graph G =(X,E)is the adjacency matrix defined as follows: setting X = {x₁,...,x_n},this is the square matrix of order n, M =(m_ij ), where m_ij is the number of edges having xi and x_j for endvertices in G. Such implementation of a graph takes memory space of the order n²,where n is the numberof vertices of the graph. Taking into account that processing the graph takes at least the time needed to read its data, this means that any algorithm over graphs modeled after an adjacency matrix will require time complexity of at least O(n²). Nevertheless, as we will see later, for some algorithms the processing in itself has a complexity of lesser order, for example O(n), therefore this model is not always appropriate.

2. A second principle for implementing a graph is to give for each vertexits “neighborhood”: the vertices which are its neighbors or its incident edges or even both, that is its incident edges and their endvertices. This last method will be particularly useful when there are multiple edges.

Implementing this can be done in various ways, the most classic, from a programming point of view, is to give, for example, the neighbors in a list called an adjacency list or list of neighbors. If we want to modify the graph during its processing, it is best to implement these lists under the classic form of linked lists. Data in lists of neighbors makes it possible to search one after the other for the neighbors of each vertex, which is a classic situation for algorithms of graphs. Some times it is possible to take a less structured processing approach and give simply the set of the neighbors N(x) for each vertex x .The memory space necessary for this type of implementation is of the order n + m, where n is the number of vertices and m the number of edges of the graph. Such a model is coherent with linear processing.

3. If in an algorithm the entry to the graph is done by the edges and not directly by the vertices, as in the above models, a third implementation principle consists of giving a list of edges with, for each of them, its endvertices . Such a list may be linked, which makes it possible to modify the graph being processed. The memory space necessary for this type of model is minimal since it is of the order of the number of edges m of the graph (note that the isolated vertices do not appear in this implementation, since they are not endvertices of an edge, by definition).

Figure 1.1 shows, for a simple graph, these models in some specific cases of the three principles above. Adjacency matrices and list of edges, as arrays, can be understood easily. Lists of neighbors are drawn as linked lists. The principle of a linked list, a classic structure in algorithms and programming,

                                      Figure 1.1. Various representations of a simple graph inside a machine

Is that each item of the list is associated with the address of the next item, an address which is called a pointer. Each item of the list is represented by a rectangle with two boxes: in the first one the neighbor is given and in the other the pointer to the following item. The pointer is represented by a circle with an arrow (pointing towards the next item). A circle without an arrow indicates the end of a list or an empty list since there is no following item.

For example, we read that the neighbors of vertex 1 are: 2, 3, or that vertex5 has no neighbor (empty list). Note that in this representation of lists of neighbors, the arrows have nothing to do with the edges of the graph. These principles are basic and in specific cases more precise information may be necessary. In addition to the above descriptions, more specific models may be defined for some applications.

In graph applications, in particular in optimization, weighted graphs are often considered, that is graphs with values, integer or real, positive or not, associated with the edges. Formally, we have a graph G =(X, Y )with a mapping v : E → R.

When a weighted graph is a simple graph, which is often the case, its computer model is generally a matrix, such as the adjacency matrix, but with entries being the values of the edges under consideration. We choose a special number, for example ∞, when there are no edges joining the vertices associated with this entry of the matrix. Specifically, using the above notation, it is the matrix M =(v(x_ix_j )), where 1 ≤ i, j ≤ n, with mapping v extended by stating: v(x_ix_j )= ∞ when i≠j and x_ix_j  ∉ E, v(x_ix_j )=0 when i = j. This matrix is symmetric.

It is also possible to use the list of edges to represent weighted graphs, by adding for each edge x_ix_j the data of its value v(x_ix_j ). In practice, it is possible to define an array indexed on the “edge” type of the graph. This type is defined as an interval of integers by numbering the edges from 1 to m, and by associating with each edge a record containing three fields: two for the endvertices of the edge and one for its value.

The list of neighbors is a priori less adapted to represent weighted graphs .Nevertheless, it is possible in the case of simple weighted graphs to add for each neighbor the data of the value of the corresponding edge.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(38-41)