Graph

What is Graph?

A graph can be defined as group of vertices and edges that are used to connect these vertices.
A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex
relationship among them instead of having parent child relationship.

A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices
and E(G) represents the set of edges which are used to connect these vertices.

A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D),
(D,B), (D,A)) is shown in the following figure.

Directed and Undirected Graph:

A graph can be directed or undirected. However, in an undirected graph, edges are not
associated with the directions with them. An undirected graph is shown in the above figure
since its edges are not attached with any of the directions. If an edge exists between vertex A
and B then the vertices can be traversed from B to A as well as A to B.

In a directed graph, edges form an ordered pair. Edges represent a specific path from some
vertex A to another vertex B. Node A is called initial node while node B is called terminal
node.

A directed graph is shown in the following figure.

Some Basic Graph Terminology:

Path
A path can be defined as the sequence of nodes that are followed in order to reach some
terminal node V from the initial node U.
Closed Path
A path will be called as closed path if the initial node is same as terminal node. A path will be
closed path if V0=VN.
Simple Path
If all the nodes of the graph are distinct with an exception V 0=VN, then such path P is called
as closed simple path.
Cycle
A cycle can be defined as the path which has no repeated edges or vertices except the first
and last vertices.
Connected Graph
A connected graph is the one in which some path exists between every two vertices (u, v) in
V. There are no isolated nodes in connected graph.
Complete Graph
A complete graph is the one in which every node is connected with all other nodes. A
complete graph contain n(n-1)/2 edges where n is the number of nodes in the graph.
Weighted Graph
In a weighted graph, each edge is assigned with some data such as length or weight. The
weight of an edge e can be given as w(e) which must be a positive (+) value indicating the
cost of traversing the edge.
Digraph
A digraph is a directed graph in which each edge of the graph is associated with some
direction and the traversing can be done only in the specified direction.
Loop
An edge that is associated with the similar end points can be called as Loop.
Adjacent Nodes
If two nodes u and v are connected via an edge e, then the nodes u and v are called as
neighbours or adjacent nodes.
Degree of the Node
A degree of a node is the number of edges that are connected with that node. A node with
degree 0 is called as isolated node.

Representation of Graph
Adjancency Matrix
Adjancency List

Adjacency matrix for a unweighted directed graph

In a directed graph, edges represent a specific path from one vertex to another vertex.
Suppose a path exists from vertex A to another vertex B; it means that node A is the initial
node, while node B is the terminal node.
Consider the below-directed graph and try to construct the adjacency matrix of it.

In the above graph, we can see there is no self-loop, so the diagonal entries of the adjacent
matrix are 0.

Adjacency matrix for a weighted directed graph

It is similar to an adjacency matrix representation of a directed graph except that instead of

using the '1' for the existence of a path, here we have to use the weight associated with the
edge. The weights on the graph edges will be represented as the entries of the adjacency
matrix. We can understand it with the help of an example. Consider the below graph and its
adjacency matrix representation. In the representation, we can see that the weight associated
with the edges is represented as the entries in the adjacency matrix.
In the above image, we can see that the adjacency matrix representation of the weighted
directed graph is different from other representations. It is because, in this representation, the
non-zero values are replaced by the actual weight assigned to the edges.

Adjacency matrix is easier to implement and follow. An adjacency matrix can be used when
the graph is dense and a number of edges are large.

Though, it is advantageous to use an adjacency matrix, but it consumes more space. Even if
the graph is sparse, the matrix still consumes the same space.

Linked list representation of Graph

An adjacency list is used in the linked representation to store the Graph in the computer's
memory. It is efficient in terms of storage as we only have to store the values for edges.

Let's see the adjacency list representation of an undirected graph.

In the above figure, we can see that there is a linked list or adjacency list for every node of
the graph. From vertex A, there are paths to vertex B and vertex D. These nodes are linked to
nodes A in the given adjacency list.

An adjacency list is maintained for each node present in the graph, which stores the node
value and a pointer to the next adjacent node to the respective node. If all the adjacent nodes
are traversed, then store the NULL in the pointer field of the last node of the list.
The sum of the lengths of adjacency lists is equal to twice the number of edges present in an
undirected graph.

Now, consider the directed graph, and let's see the adjacency list representation of that graph.