Graph (data structure) - AbsoluteAstronomy.com

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a graph is an abstract data structure that is meant to implement the graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

and hypergraph

Hypergraph

In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...

concepts from mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

.

A graph data structure consists of a finite (and possibly mutable) set

Set (computer science)

In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...

of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or reference

Reference (computer science)

In computer science, a reference is a value that enables a program to indirectly access a particular data item, such as a variable or a record, in the computer's memory or in some other storage device. The reference is said to refer to the data item, and accessing those data is called...

s.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Algorithms

Graph algorithms are a significant field of interest within computer science. Typical higher-level operations associated with graphs are: finding a path between two nodes, like depth-first search

Depth-first search

Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....

and breadth-first search

Breadth-first search

In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...

and finding the shortest path from one node to another, like Dijkstra's algorithm

Dijkstra's algorithm

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...

. A solution to finding the shortest path from each node to every other node also exists in the form of the Floyd-Warshall algorithm

Floyd-Warshall algorithm

In computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...

.

A directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

can be seen as a flow network

Flow network

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...

, where each edge has a capacity and each edge receives a flow. The Ford-Fulkerson algorithm

Ford-Fulkerson algorithm

The Ford–Fulkerson Method computes the maximum flow in a flow network. It was published in 1956...

is used to find out the maximum flow

Maximum flow problem

In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....

from a source to a sink in a graph.

Operations

The basic operations provided by a graph data structure G usually include:

adjacent(G, x, y): tests whether there is an edge from node x to node y.
neighbors(G, x): lists all nodes y such that there is an edge from x to y.
add(G, x, y): adds to G the edge from x to y, if it is not there.
delete(G, x, y): removes the edge from x to y, if it is there.
get_node_value(G, x): returns the value associated with the node x.
set_node_value(G, x, a): sets the value associated with the node x to a.

Structures that associate values to the edges usually also provide:

get_edge_value(G, x, y): returns the value associated to the edge (x,y).
set_edge_value(G, x, y, v): sets the value associated to the edge (x,y) to v.

Representations

Different data structures for the representation of graphs are used in practice:

Adjacency list
Adjacency list
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node...

- Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices.
Incidence list
Incidence list
In graph theory, the incidence list is a variant of the adjacency list that allows for the description of the edges at the cost of additional edges. Instead of storing adjacent vertices, the list stores all of the edges that contain the referencing vertex. Edges are required to have two vertices....

- Vertices and edges are stored as records or objects. Each vertex stores its incident edges, and each edge stores its incident vertices. This data structure allows the storage of additional data on vertices and edges.
Adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...

- A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
Incidence matrix
Incidence matrix
In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related ...

- A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

The following table gives the time complexity

Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...

cost of performing various operations on graphs, for each of these representations. In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be

	Adjacency list	Adjacency matrix	Incidence matrix
Storage
Add vertex
Add edge
Remove vertex
Remove edge
Query: are vertices u, v adjacent? (Assuming that the storage positions for u, v are known)
Remarks	When removing edges or vertices, need to find all vertices or edges	Slow to add or remove vertices, because matrix must be resized/copied	Slow to add or remove vertices and edges, because matrix must be resized/copied

Adjacency lists are generally preferred because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges E is close to the number of vertices squared, V², or if one must be able to quickly look up if there is an edge connecting two vertices.

External links

Boost Graph Library: a powerful C++ graph library

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Algorithms

Operations

Representations

See also

External links