Graph (abstract data type)
Definition
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics. 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 or arcs. As in mathematics, an edge (x, y) is said to point or go from x to y. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
Characteristics
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.). The basic operations provided by a graph data structure G usually include:
- adjacent(G, x, y): tests whether there is an edge from the vertices x to y;
- neighbors(G, x): lists all vertices y such that there is an edge from the vertices x to y;
- add(G, x, y): adds to G the edge from the vertices x to y, if it is not there;
- delete(G, x, y): removes the edge from the vertices x to y, if it is there;
- get_node_value(G, x): returns the value associated with the vertex x;
- set_node_value(G, x, a): sets the value associated with the vertex x to a.
Structures that associate values to the edges usually also provide:
- get_edge_value(G, x, y): returns the value associated to the edge (x, y);
- set_edge_value(G, x, y, v): sets the value associated to the edge (x, y) to v.
Types of Graphs
There are different types of graphs, which are classified based on their properties. Some of these types include:
- Undirected Graphs: A graph in which edges have no orientation. The edge (x, y) is identical to the edge (y, x).
- Directed Graphs: A graph in which edges have orientations.
- Weighted Graphs: A graph in which each edge is assigned a weight or cost.
- Cyclic Graphs: A graph containing at least one graph cycle.
- Acyclic Graphs: A graph with no graph cycles.
- Connected Graphs: In an undirected graph, a graph is connected if there is a path between every pair of vertices. In a directed graph, a graph is strongly connected if there is a path in each direction between each pair of vertices of the graph.
- Disconnected Graphs: Graphs that are not connected are disconnected.
Graph Representation
Graphs can be represented in data structures in various ways, depending on the specific use case at hand. The two most common types of graph representations are:
- Adjacency Matrix: A square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
- Adjacency List: A collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.
Applications of Graphs
Graphs are among the most ubiquitous models of both natural and human-made structures. They can represent many types of systems, including physical, biological, social, and informational. Some examples of applications of graphs include:
- Network Topologies: Graphs can be used to represent network topologies, such as local area networks (LANs), wide area networks (WANs), and the internet.
- Social Networks: Social networks can be modeled using graphs, where vertices represent individuals or entities, and edges represent relationships or interactions between them.
- Web Graphs: The structure of the World Wide Web can be represented as a graph, with web pages as vertices and hyperlinks as edges.
- Transport Networks: Graphs can be used to represent transport networks, such as roads, railways, and air routes, where vertices represent locations and edges represent routes between locations.
- Biological Networks: In biology, graphs can be used to represent networks of interactions, such as protein-protein interaction networks, genetic interaction networks, metabolic networks, and food webs.