In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory.
A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
Maps, Directions, and Place Reviews
Operations
The basic operations provided by a graph data structure G usually include:
adjacent(G, x, y): tests whether there is an edge from the vertex x to the vertex y;neighbors(G, x): lists all vertices y such that there is an edge from the vertex x to the vertex y;add_vertex(G, x): adds the vertex x, if it is not there;remove_vertex(G, x): removes the vertex x, if it is there;add_edge(G, x, y): adds the edge from the vertex x to the vertex y, if it is not there;remove_edge(G, x, y): removes the edge from the vertex x to the vertex y, if it is there;get_vertex_value(G, x): returns the value associated with the vertex x;set_vertex_value(G, x, v): sets the value associated with the vertex x to v.
Structures that associate values to the edges usually also provide:
get_edge_value(G, x, y): returns the value associated with the edge (x, y);set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.
Computer Science Graph Video
Representations
Different data structures for the representation of graphs are used in practice:
The following table gives the time complexity cost of performing various operations on graphs, for each of these representations, with |V | the number of vertices and |E | the number of edges. In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be ?.
Adjacency lists are generally preferred because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges |E | is close to the number of vertices squared, |V |2, or if one must be able to quickly look up if there is an edge connecting two vertices.
Source of the article : Wikipedia
EmoticonEmoticon