Representation of Graph

Representation of Graph

There various representations of graphs. The most commonly used representations are

1. Adjacency Matrix Representation

2. Adjacency List Representation

Adjacency Matrix

Consider a graph G of n vertices and the matrix M. If there is an edge present between vertices V_i and V_j then M[i][j] = 1 else M[i][j] = 0. Note that for an undirected graph if M[i][j] =1 then for M[j][i] is also 1. Here are some graphs sh own by adjacency matrix.

Creating a Graph using Adjacency Matrix

Creation of graph using adjacency matrix is quite simple task. The adjacency matrix is nothing but a two dimensional array. The algorithm for creation of graph using adjacency matix will be as follows:

1) Declare an array of M[size] [size] which will store the graph.

2) Enter how many nodes you want in a graph.

3) Enter the edges of the graph by two vertices each, say V_i, V_j indicates some edge.

4) If the graph is directed set M[i][j]=1. If graph is undirected set M[i][j] = 1 and M[j][i]= 1 as well.

5) When all the edges for the desired graph is entered print the graph M[i][j].

Adjacency List

The type of representation of a graph in which the linked list is used, is called Adjacency 

List representation.

There are two methods of representing the adjacency list.

Method 1:

For graph G in Fig. 5.5.2, the nodes as a, b, c, d, e. So we will maintain the linked list of these head nodes as well as the adjacent nodes. The 'C' structure will be

typedef struct head

}

char data;

struct head *down;

struct head *next;

}

typedef struct node

{

int ver;

struct node *link;

}

Explanation: This is purely the adjacency list graph. The down pointer helps us to go to each node in the graph whereas the next node is for going to adjacent node of each of the head node.

 Method 2: In this method of representing the adjacency list, we take mixed data structure. That means instead of taking the head list as a linked list we will take an array of head nodes. So only one 'C' structure will be there representing the adjacent nodes. See the

Fig. 5.5.4 representing the adjacency list for the above graph. First let us see the 'C' structure.

typedef struct node1

{

char vertex;

struct node1 *next

}node

node * head [5]

Explanation: This is the graph which can be represented with the array and linked list data structures. Array is used to store the head nodes. The node strucutre will be the same through out.

Ex. 5.5.1 What do you mean adjacency matrix and adjacency list ? Give the adjacency matrix and adjacency list of the following graph:

Sol. Adjacency matrix and Adjacency list

Adjacency Matrix for given graph

Adjacency List for given graph

Ex. 5.5.2 Represent following graph using adjacency matrix and adjacency list.

Ex. 5.5.3 Draw the adjacency list of the graph given in Fig. 5.5.6.

Ex. 5.5.4 Write an algorithm to find indegree and outdegree of a vertex in a given graph.

Sol

1. Initialize indegree and outdegree count for each node to zero.

2. Visit each node of a graph.

3. Count the number of incoming edges of each node and then increment indegree count by one for each incoming each.

4. Count the number of outgoing edges of each node and then increment outdegree count by one on each outgoing edge.

Ex. 5.5.5 Write a function to print indegree, outdegree and total degree of given vertex. Sol. :

void print_degree()

{

int v;

for(v=0;v<n;v++)

{

in=indegree(v,n);

out outdegree(v,int n);

total=in+out;

printf("\n The indegree for vertex %d is %d",v,in); game jar

printf("\n The outdegree for vertex %d is %d",v,out);

printf("\n The total degree for vertex %d is %d",v,total);

}

int indegree(int v,n)

{

int v1,count=0;

for(v1=0;v1<n;v1++)

if(a[v1][v] ==1)

count++;

return count;

}

int outdegree(int v,int n)

{

int v2,count=0;

for(v2=0;v2<n;v2++)

if(a[v][v2]==1).

.count++;

return count;

}

Ex. 5.5.6 Explain with example inverse adjacency list representation of graph. Consider following graph.

Ex. 5.5.7 Give the adjacency matrix and adjacency

list representation for the graph shown in following Fig. 5.5.7.