Introduction of Representation of Graph
 Graphs are believed to be a way of expressing relationships between pairs of items and are one of the most important abstractions in computer science.
Definition
 The representation of a graph is a way to store graphical format inside the computer’s memory in the binary form either statically or dynamically.
Characteristics
 The representation of the graph occurs in sequence in memory.
Types
 There are two common ways to represent graphs in a computer’s memory. These are as follows:
 Adjacency matrix(as Array)
 Adjacency list(as Linked List)
Adjacency Matrix

 Adjacency Matrix is the representation of a graph inside memory in the form of a 2D array/matrix of size V x V (where V is the number of vertices available in a graph).
 An adjacency matrix is applied for both directed or undirected as well as weighted or nonweighted graphs.
 The adjacency matrix for undirected graphs is always symmetric.
 In a weighted graph, adj[i][j] = w i.e., there is an existence of edge from vertex i to vertex j with weight value w in their matrix representation but for nonweighted graph instead of weight values we use 1s for edge existing and 0s for no edge existing.
 It is easier to implement and follow.
 The matrix representation easily determines the connection of vertices in the graph.
 This representation consumes more space O(V^{2}).
Adjacency Lists

 Adjacency Lists is the representation of a graph inside memory in the form of an array of Linked Lists.
 An array of lists is used. The size of the array is equal to the number of vertices.
 Adjacency Lists are applied for both directed or undirected as well as weighted or nonweighted graphs.
 The weights of edges can be represented as lists of pairs.
 This representation saves memory space and time.
 It can be represented in two forms. In one form, the array is used to store n vertices, and the chain is used to store its adjacencies/edges.
 Adding a new vertex/data value is easier in adjacency lists.
 Traversing all the neighbors’ vertex from a source takes optimal time.
Use/Application
 The Graph representation is used in statistical work to determine, relate, and compare different data. This gives various information in facts and figures for analysis
0 Comments