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