NIST

graph

(data structure)

Definition: A set of items connected by edges. Each item is called a vertex or node. Formally, a graph is a set of vertices and a binary relation between vertices, adjacency.

Formal Definition: A graph G can be defined as a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u,v) | u, v ∈ V}. If the graph is undirected, the adjacency relation defined by the edges is symmetric, or E ⊆ {{u,v} | u, v ∈ V} (sets of vertices rather than ordered pairs). If the graph does not allow self-loops, adjacency is irreflexive.

Specialization (... is a kind of me.)
directed graph, undirected graph, acyclic graph, directed acyclic graph, planar graph, connected graph, biconnected graph, bipartite graph, complete graph, dense graph, sparse graph, hypergraph, multigraph, labeled graph, weighted graph, tree.

Aggregate child (... is a part of or used in me.)
vertex, edge, Implementations: adjacency-list representation, adjacency-matrix representation.

See also Relations between vertices: adjacent, self-loop, Relations between graphs: isomorphic, homeomorphic, dual, subgraph, Properties: diameter, degree, Other: graph drawing, graph partition.

Note: Graphs are so general that many other data structures, such as trees, are just special kinds of graphs.

A graph is like a road map. Cities are vertices. Roads from city to city are edges. (How about junctions or branches in a road? You could consider junctions to be vertices, too. If you don't want to count them as vertices, a road may connect more than two cities. So strictly speaking you have hyperedges in a hypergraph. If you want to allow more than one road between each pair of cities, you have a multigraph, instead. It all depends on how you want to define it.)

Another way to think of a graph is as a bunch of dots connected by lines. Because mathematicians stopped talking to regular people long ago, the dots in a graph are called vertices, and the lines that connect the dots are called edges. The important things are edges and the vertices: the dots and the connections between them. The actual position of a given dot or the length or straightness of a given line isn't at issue. Thus the dots can be anywhere, and the lines that join them are infinitely stretchy. Moreover, a mathematical graph is not a comparison chart, nor a diagram with an x- and y-axis, nor a squiggly line on a stock report. A graph is simply dots and lines between them---pardon me, vertices and edges.
    Michael Bolton <mb@michaelbolton.net> 22 February 2000

Authors: PEB,PJT

Implementation

GraphEd -- Graph Editor and Layout Program (C), graph manipulation (C++, C, Mathematica, and Pascal), JGraphT (Java) build, traverse, and display directed and undirected graphs, GEF - Graph Editing Framework (Java) a library to edit and display graphs. Graph generating (C, Mathematica, Pascal, C++, and Fortran), BGL - the Boost Graph Library (C++). GTL - the Graph Template Library (C). Annas (Java), for graph theory, AI, path finding, distributed systems, etc. The main libraries are Annas.Graph, graph manipulation and visualization and Annas.Math, comprehensive math functions. JUNG (Java), the Java Universal Network/Graph framework. JDSL (Java), the Data Structures Library in Java. Algorithms and Data Structures' explanation and adjacency matrix implementation (Java and C++).

More information

Journal of Combinatorics dynamic surveys DS8 and DS9 are a bibliography and glossary of graphs. Deepayan Chakrabarti and Christos Faloutsos, Graph Mining: Laws, Generators, and Algorithms, ACM Computing Surveys, Vol. 38, March 2006, Article 2.
A great list of graph generators and their strengths and weaknesses.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 26 December 2012.
HTML page formatted Tue May 6 13:48:55 2014.

Cite this as:
Paul E. Black and Paul J. Tanenbaum, "graph", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 26 December 2012. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/graph.html