- Graph (data structure)
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 graphis 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 networkcan be modeled with a graph.
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 searchand breadth-first searchand 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 algorithmis 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
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
* [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
* [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.