Graph (data structure)
Encyclopedia

In computer science
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 Incidence 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, V2, or if one must be able to quickly look up if there is an edge connecting two vertices.

See also

  • Graph traversal
    Graph traversal
    Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal...

     for graph walking strategies
  • Graph database
    Graph database
    A graph database uses graph structures with nodes, edges, and properties to represent and store data. By definition, a graph database is any storage system that provides index-free adjacency. General graph databases that can store any graph are distinct from specialized graph databases such as...

     for graph (data structure) persistency
  • Graph rewriting
    Graph rewriting
    Graph transformation, or Graph rewriting, concerns the technique of creating a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms....

     for rule based transformations of graphs (graph data structures)
  • GraphStream
    GraphStream
    -External links:* * *...

  • Graphviz
    Graphviz
    Graphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...

  • yEd
    YEd
    yEd is a freely available, general-purpose diagramming software with amulti-document interface.It is a cross-platform application written in Java that runs on Windows, Linux, Mac OS, or any platform that supports the JVM....

    Graph Editor - Java-based diagram editor for creating and editing graphs

External links

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