Graph (data structure)

Graph (data structure)

In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes (also called vertices) and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.

Informally, "G=(V,E)" consists of "vertices", the elements of "V", which are connected by "edges", the elements of "E". Formally, a graph, "G", is defined as an ordered pair, "G=(V,E)", where "V" is a set (usually finite) and "E" is a set consisting of two element subsets of "V".

Choices of representation

Two main data structures for the representation of graphs are used in practice. The first is called an adjacency list, and is implemented by representing each node as a data structure that contains a list of all adjacent nodes. The second is an adjacency matrix, in which the rows and columns of a two-dimensional array represent source and destination vertices and entries in the array indicate whether an edge exists between the vertices. Adjacency lists are preferred for sparse graphs; otherwise, an adjacency matrix is a good choice. Finally, for very large graphs with some regularity in the placement of edges, a symbolic graph is a possible choice of representation.

Comparison with other data structures

Graph data structures are non-hierarchical and therefore suitable for data sets where the individual elements are interconnected in complex ways. For example, a computer network can be modeled with a graph.

Hierarchical data sets can be represented by a binary or nonbinary tree. It is worth mentioning, however, that trees can be seen as a special form of graph.

Operations

Graph algorithms are a significant field of interest within computer science. Typical operations associated with graphs are: finding a path between two nodes, like depth-first search and breadth-first search and finding the shortest path from one node to another, like Dijkstra's algorithm. A solution to finding the shortest path from each node to every other node also exists in the form of the Floyd-Warshall algorithm.

A directed graph can be seen as a flow network, where each edge has a capacity and each edge receives a flow. The Ford-Fulkerson algorithm is used to find out the maximum flow from a source to a sink in a graph.

The graphs can be represented in two ways. One is adjacency matrix and adjacency list.

For example, let us consider the following graph

A----------->B
^


V
C ------------

Adjacency Matrix A B C A 0 1 1 B 0 0 0 C 0 1 0

Adjacency List A ----> | B | ----> | C | ---- NULL B ----> ---- NULL C ----> | B | ---- NULL

External links

* [http://student.seas.gwu.edu/~idsv/idsv.html Interactive visualisations] (not working with Mozilla Firefox) of graphs and other data structures.
* [http://hamilton.bell.ac.uk/swdev2/notes/notes_18.pdf Notes] (PDF, 280 KiB)
* [http://www.boost.org/libs/graph Boost Graph Library: a powerful C++ graph library]
* [http://search.cpan.org/search?query=Graph&mode=all Perl graph routines]
* [http://www.codeplex.com/quickgraph QuickGraph: Graph Data Structures And Algorithms for .NET]
* [http://algraf.es.kz Algraf Project: Graphical tool to draw graphs, apply several algorithms to them and export to XML]
* [http://www.graphviz.org/ Graphviz - Graph Visualization Software (Open Source)]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Data structure — In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2] Different kinds of data structures are suited to different kinds of applications, and some are highly …   Wikipedia

  • data structure — noun An organization in software of data that allows more optimal searching, categorizing, or storage of information. Examples: matrix, stack, queue, dequeue, list …   Wiktionary

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Persistent data structure — In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in… …   Wikipedia

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Container (data structure) — For the abstract notion of containers in Type theory, see Container (Type theory). In computer science, a container is a class, a data structure[1][2], or an abstract data type (ADT) whose instances are collections of other objects. In other… …   Wikipedia

  • Zipper (data structure) — Zipper is a purely functional data structure used in functional programming to solve some problems in a way using notions like “context” and “hole”. It is related to the generalization of notion “derivative” (for types). The zipper was described… …   Wikipedia

  • Succinct data structure — In computer science, a succinct data structure for a given data type is a representation of the underlying combinatorial object that uses an amount of space “close” to the information theoretic lower bound together with efficient algorithms for… …   Wikipedia

  • Disjoint-set data structure — In computing, a disjoint set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union find algorithm is an algorithm that performs two useful operations on… …   Wikipedia

  • Graph — may refer to:* A graphic (such as a chart or diagram) depicting the relationship between two or more variables used, for instance, in visualising scientific data.In mathematics:* Graph (mathematics), a set of vertices connected with edges * Graph …   Wikipedia