Graph (data structure)
In computer science, a graph is an abstract data type that consists of nodes or vertices connected with edges. It is an implementation of the abstract model of a graph from mathematics. In practice, the nodes are generally implemented as structures or objects; there are several ways to represent the edges, each of which has advantages and disadvantages.
One of these ways is to equip each node with an array of out-going 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 out-going edges per node. Finding shortest paths between nodes requires Dijkstra's algorithm.
An alternative way is to keep a 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 Mi,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 two nodes can be determined using directed acyclic word graph, a method of encoding a word-list for computer versions of word games such as Scrabble. A very simple example of an acyclic graph is a 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.
