Graph Representation

Representation of Graph

Generally graph can be represented in two ways namely adjacency lists(Linked list representation) and adjacency matrix(matrix).

Adjacency List: 

This type of representation is suitable for the undirected graphs without multiple edges, and directed graphs. This representation looks as in the tables below.

If we try to apply the algorithms of graph using the representation of graphs by lists of edges, or adjacency lists it can be tedious and time taking if there are high number of edges.

For the sake of the computation, the graphs with many edges can be represented in other ways. In this class we discuss two ways of representing graphs in form of matrix.

Adjacency Matrix: 

Given a simple graph G =(V, E) with |V| = n. assume that the vertices of the graph are listed in some arbitrary order like v1, v2, …, vn. The adjacency matrix A of G, with respect to the order of the vertices is n-by-n zero-one matrix (A = [aij]) with the condition,

Since there are n vertices and we may order vertices in any order there are n! possible order of the vertices. The adjacency matrix depends on the order of the vertices, hence there are n! possible adjacency matrices for a graph with n vertices. In case of the directed graph we can extend the same concept as in undirected graph as dictated by the relation

If the number of edges is few then the adjacency matrix becomes sparse. Sometimes it will be beneficial to represented graph with adjacency list in such a condition.

Solution:Let the order of the vertices be a, b, c, d, e, f

Let us take a directed graph

Solution:

Let the order of the vertices be a, b, c, d, e, f, g