Graph (data structure)

From Wikipedia, the free encyclopedia

A labeled graph on 6 vertices and 7 edges.

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

A graph G is defined as follows: G=(V,E), where V is a finite, non-empty set of vertices (singular: vertex) and E is a set of edges (links between pairs of vertices). When the edges in a graph have no direction, the graph is called undirected, otherwise called directed. In practice, some information is associated with each node and edge.

1 Choices of representation
2 Comparison with other data structures
3 Operations
4 See also
5 External links

[edit] 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 graph 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.

[edit] 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 simulated 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.

[edit] Operations

Graph algorithms are a significant field of interest for computer scientists. 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.