Graph (data structure)

Encyclopedia : G : GR : GRA : Graph (data structure)

In computer science, a graph is an abstract data type (ADT) that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.

A graph G is defined as follows: G=(V,E), where V is a finite, non-empty set of vertices and E is a set of edges (links between pairs of vertices). When the edges in a graph have no direction, the graph is called undirected, otherwise called directed. In practice, some information is associated with each node and edge.

Representation

In typical graph implementations, nodes are implemented as structures or objects. There are several ways to represent edges, each with advantages and disadvantages:

As an adjacency list

An adjacency list associates each node with an array of incident edges. If no information is required to be stored in edges, only in nodes, these arrays can simply be pointers to other nodes and thus represent edges with little memory requirement. An advantage of this approach is that new nodes can be added to the graph easily, and they can be connected with existing nodes simply by adding elements to the appropriate arrays. A disadvantage is that determining whether an edge exists between two nodes requires O(n) time, where n is the average number of incident edges per node.

As an adjacency matrix

An alternative way is to keep a square matrix (a two-dimensional array) M of boolean values (or integer values, if the edges also have weights or costs associated with them). The entry M_i,j then specifies whether an edge exists that goes from node i to node j. An advantage of this approach is that finding out whether an edge exists between two nodes becomes a trivial constant-time memory look-up. Similarly, adding or removing an edge is a constant-time memory access. The shortest path between any two nodes can be determined using the Floyd-Warshall algorithm. A disadvantage is that adding or removing nodes from the graph requires re-arranging the matrix accordingly, which may be costly depending on its size.

Other representations

Yet another way is based on keeping a relation (table) of edges, with key (source, target), where source and target are the connected vertices. Known algorithms allow the table to be manipulated and searched in loglinear time. Mneson [link] takes this approach.

In the general case, a graph may consist of many edges between many vertices, and unless the matrix representation for the edges is chosen, there may even be more than one edge connecting the same pair of vertices. Edges can be bidirectional or unidirectional.

Most data structures that are graphs are more structured than the general graph. A graph may, for example, be acyclic. In this case, each edge is unidirectional, and there is no way to traverse the edges in such a way as to ever visit the same node twice. An example of an acyclic graph is a directed acyclic word graph, a method of encoding a word-list for computer versions of word games such as Scrabble. A simple example of an acyclic graph is a non-circular singly linked list.

In most cases, the only information contained by the edge is that there is a relationship between the two nodes connected, and the information is stored in the node itself. However, some graphs have numerical values associated with each edge. These graphs can be used for different problems such as the Traveling salesman problem.

Additionally, there are graph-like structures where information is kept in the edges. One data structure has all of the information in the edges, and none of the information is in the nodes. This data structure can be very useful in modelling things like the pipes in a factory, or the wires in an airplane.

Operations

Graph algorithms are a significant field of interest for computer scientists. Typical operations associated with graphs are: finding a path between two nodes, like depth-first search and breadth-first search and finding the shortest path from one node to another, like Dijkstra's algorithm.

Graph (data structure)

Representation

Operations

See also