World Library  
Flag as Inappropriate
Email this Article

Graph (abstract data type)

Article Id: WHEBN0000557931
Reproduction Date:

Title: Graph (abstract data type)  
Author: World Heritage Encyclopedia
Language: English
Subject: Data structure, Network science, Data structures, Graph Theory, Abstract data type
Collection: Abstract Data Types, Graph Data Structures, Graph Theory, Graphs, Hypergraphs
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Graph (abstract data type)

A graph with three vertices and three edges.

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics.

A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges or arcs or lines for an undirected graph and as arrows or directed edges or directed arcs or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

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.).

Contents

  • Algorithms 1
  • Operations 2
  • Representations 3
  • See also 4
  • References 5
  • External links 6

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 vertices, like depth-first search and breadth-first search and finding the shortest path from one vertex to another, like Dijkstra's algorithm. A solution to finding the shortest path from each vertex to every other vertex also exists in the form of the Floyd–Warshall algorithm.

Operations

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

  • adjacent(G, x, y): tests whether there is an edge from the vertices x to y;
  • neighbors(G, x): lists all vertices y such that there is an edge from the vertices x to y;
  • add_vertex(G, x): adds the vertex x, if it is not there;
  • remove_vertex(G, x): removes the vertex x, if it is there;
  • add_edge(G, x, y): adds the edge from the vertices x to y, if it is not there;
  • remove_edge(G, x, y): removes the edge from the vertices x to y, if it is there;
  • get_vertex_value(G, x): returns the value associated with the vertex x;
  • set_vertex_value(G, x, v): sets the value associated with the vertex x to v.

Structures that associate values to the edges usually also provide:

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

Representations

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

Adjacency list
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. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
Adjacency matrix
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
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 cost of performing various operations on graphs, for each of these representations, with |V | the number of vertices and |E | the number of edges. 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
Store graph O(|V|+|E|) O(|V|^2) O(|V|\cdot|E|)
Add vertex O(1) O(|V|^2) O(|V|\cdot|E|)
Add edge O(1) O(1) O(|V|\cdot|E|)
Remove vertex O(|E|) O(|V|^2) O(|V|\cdot|E|)
Remove edge O(|E|) O(1) O(|V|\cdot|E|)
Query: are vertices x and y adjacent? (assuming that their storage positions are known) O(|V|) O(1) O(|E|)
Remarks Slow to remove vertices and edges, because it needs 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 |2, or if one must be able to quickly look up if there is an edge connecting two vertices.[1]

See also

References

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw–Hill. ISBN 0-262-53196-8.

External links

  • Boost Graph Library: a powerful C++ graph library
  • Networkx: a Python graph library
  • Graphs Tutorial by Jebril FILALI
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.