# Graph (data structure)

Translation- Graph (data structure)
In

computer science , a**graph**is a kind ofdata structure , specifically anabstract 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 frommathematics .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 anadjacency 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 forsparse graph s; otherwise, an adjacency matrix is a good choice. Finally, for very large graphs with some regularity in the placement of edges, asymbolic 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 andbreadth-first search and finding the shortest path from one node to another, likeDijkstra's algorithm . A solution to finding the shortest path from each node to every other node also exists in the form of theFloyd-Warshall algorithm .A directed graph can be seen as a

flow network , where each edge has a capacity and each edge receives a flow. TheFord-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 withMozilla Firefox ) of graphs and other data structures.

* [*http://hamilton.bell.ac.uk/swdev2/notes/notes_18.pdf Notes*] (PDF, 280KiB )

* [*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