In this tutorial, you will learn an important data structure, Graph. You will also discover basic terminology, types of graphs, how graphs are represented in memory and their applications.
A graph is a non-linear data structure consisting of vertices and edges that connect these vertices.
Definition
A graph is an ordered set G = (V, E) consist of two sets: V and E, where
- V is the set of nodes (vertices, points or nodes)
- E is the set of edges, identified with a unique pair of nodes in V, denoted by
e=(u, v).
The following figure shows an example of a graph where V(G) = {A, B, C, D, E} and E(G) = { (A,B), (B,C), (C,D), (D,E), (E,A), (A,D) }
Graph Terminology
Let e = [u, v]. Then nodes u and v are referred to as endpoints of e, and u and v are referred to as adjacent nodes or neighbours.
The number of edges containing u is the degree of node u.
If u does not belong to any edge (degree of u = 0), then u is referred to as an isolated edge.
A finite sequence of edges that connects a series of vertices is called a path.
The number of edges in a path is the length of the path.
A path is said to be closed if it starts and ends at the same node.
A path is considered to be simple if all of its nodes are distinct, except the initial and last node.
A cycle is a closed simple path with a length of 3 or more.
A graph is considered to be connected if and only if any two of its nodes have a path between them.
If every node u in a graph is adjacent to every other node v in the graph, then the graph is said to be complete.
An edge e is called a loop if it has identical endpoints, that is if e = [u,u].
When multiple edges in a graph connect the same pair of nodes, the edges are referred to as parallel edges.
A multigraph is a graph that contains a self-loop, parallel edges, or both.
Types of Graphs
Directed and Undirected Graph
A graph with edges that don’t have direction is called an undirected graph. The edges in an undirected graph indicate a two-way relationship.
A Directed graph(digraph) is a graph that has edges with direction. These edges represent a one-way relationship. That is edges can be only traversed in one direction.
If a digraph has a directed edge e = [u, v], then
- e begins at u, and ends at v.
- u is the origin or initial point of e, and v is the destination or terminal point of e.
The number of edges beginning at a node u is its outdegree. The number of edges that finish at a node u is its indegree. If a node u has a positive outdegree but a negative indegree, it is referred to as a source.
If a node u has a zero outdegree but a positive indegree, it is referred to as a sink.
If there is a directed path from v to u, then node v is said to be reachable from u. A directed graph G is said to be connected (strongly connected) if there is a path from u to v and also a path from v to u for each pair u, v of nodes in the graph.
Weighted Graph
A weighted graph is a graph that has a number associated with each of its edges. The number is called the weight of the edge. A weighted graph can be undirected or directed. The weight of a path P is the sum of the weights of the edges along the path.
Representation of Graphs
Graphs are typically represented in one of three ways:
Sequential Representation : Adjacency Matrix
A graph with N nodes can be represented by an NxN square matrix with row and column numbers representing the vertices. A cell at the cross-section of the vertices can only have the values 0 or 1. An entry in the adjacency matrix [Vi, Vj] = 1 only if there exists an edge from Vi to Vj. A graph and its corresponding adjacency matrix are illustrated below:
In the case of a weighted graph, the weight of the edge is saved instead of the value 1. Since the adjacency matrix will be sparse, a lot of space will be wasted. Adding or removing new nodes may be difficult.
Linked Representation
The linked representation of a graph contains two lists, a NODE list and an EDGE(Adjacency) list.
Each element in the NODE list will correspond to a node in the graph. It contains:
- Name of the Node.
- Pointer to adjacent nodes.
- Pointer to next node.
Each element in the edge list will represent an edge of the graph. It contains:
- Destination node of the edge.
- Link that link together the edges with the same initial node.
A graph and its corresponding linked representation are illustrated below.
Because we only need to keep the values for the edges, an adjacency list is efficient in terms of storage.
Applications of Graph
- In circuit networks: connection points as vertices and wires as edges.
- In transport network: stations as vertices and routes as edges.
- For finding shortest paths.
- In state diagrams: states as vertices and transition between states as edges.
- For scientific computations.
- In recommendation algorithms.