Following two are the most commonly used representations of graph.
1. Adjacency Matrix
2. Adjacency List

**Graph and
its representations**

Graph is
a data structure that consists of following two components:

**1. **A finite
set of vertices also called as nodes.

A finite
set of ordered pair of the form (u, v) called as edge. The pair is ordered
because (u, v) is not same as (v, u) in case of directed graph(di-graph). The
pair of form (u, v) indicates that there is an edge from vertex u to vertex v.
The edges may contain weight/value/cost. Graphs are used to represent many real
life applications: Graphs are used to represent networks. The networks may
include paths in a city or telephone network or circuit network. Graphs are
also used in social networks like linkedIn, facebook. For example, in facebook,
each person is represented with a vertex(or node). Each node is a structure and
contains information like person id, name, gender and locale. Following is an
example undirected graph with 5 vertices.

Following
two are the most commonly used representations of graph.

**1. **Adjacency
Matrix

**2. **Adjacency
List

There are
other representations also like, Incidence Matrix and Incidence List. The
choice of the graph representation is situation specific. It totally depends on
the type of operations to be performed and ease of use.

**Adjacency Matrix:**

Adjacency Matrix is a 2D array of size V x V where
V is the number of vertices in a graph. Let the 2D array be adj[][], a slot
adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.
Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is
also used to represent weighted graphs. If adj[i][j] = w, then there is an edge
from vertex i to vertex j with weight w. The adjacency matrix for the above
example graph is:

**Adjacency Matrix Representation of the above graph**

Pros:
Representation is easier to implement and follow. Removing an edge takes O(1)
time. Queries like whether there is an edge from vertex „u‟ to vertex „v‟ are efficient and can be

done
O(1).

Cons:
Consumes more space O(V^2). Even if the graph is sparse(contains less number of
edges), it consumes the same space. Adding a vertex is O(V^2) time.

**Adjacency List:**

An array of linked lists is used. Size of the array
is equal to number of vertices. Let the array be array[]. An entry array[i]
represents the linked list of vertices adjacent to the **i**th vertex. This representation can also be used to represent a
weighted graph. The weights of edges can be stored in nodes of linked lists.
Following is adjacency list representation of the above graph.

Below is
C code for adjacency list representation of an undirected graph:

// A C Program to demonstrate adjacency list
representation of graphs

#include <stdio.h>

#include
<stdlib.h>

//A structure to represent an adjacency list node

structAdjListNode

{

intdest;
structAdjListNode* next;

};

//A structure to represent an adjacency liat

structAdjList

{

structAdjListNode
*head; // pointer to head node of list

};

// A
structure to represent a graph. A graph is an array of adjacency lists.

// Size of
array will be V (number of vertices in graph)

structGraph

{

intV;

structAdjList*
array; };

// A utility
function to create a new adjacency list node

structAdjListNode* newAdjListNode(intdest)

{

structAdjListNode*
newNode =

(structAdjListNode*)
malloc(sizeof(structAdjListNode)); newNode->dest = dest;

newNode->next
= NULL; returnnewNode;

}

//A utility function that creates a graph of V vertices

structGraph* createGraph(intV)

{

structGraph*
graph = (structGraph*) malloc(sizeof(structGraph)); graph->V = V;

// Create an
array of adjacency lists. Size of array will be V

graph->array
= (structAdjList*) malloc(V * sizeof(structAdjList));

//Initialize each adjacency list as empty by making head as NULL inti;

for(i =
0; i< V; ++i)

graph->array[i].head
= NULL;

return graph;

}

// Adds an
edge to an undirected graph

// voidaddEdge(structGraph*
graph, intsrc, intdest)

{

// Add an
edge from src to dest. A new node is added to the adjacency

// list of
src. The node is added at the begining

structAdjListNode*
newNode = newAdjListNode(dest);

newNode->next
= graph->array[src].head;

graph->array[src].head
= newNode;

//Since graph is undirected, add an edge from dest to src also

newNode = newAdjListNode(src);

newNode->next
= graph->array[dest].head;

graph->array[dest].head
= newNode;

}

//A utility function to print the adjacenncy list representation of
graph

voidprintGraph(structGraph* graph)

{

intv;

for(v =
0; v < graph->V; ++v)

{

structAdjListNode*
pCrawl = graph->array[v].head;

printf("\n
Adjacency list of vertex %d\n head ", v);

while(pCrawl)

{

printf("->
%d", pCrawl->dest);

pCrawl =
pCrawl->next;

}

printf("\n");

}

}

//Driver program to test above functions

intmain()

{

//create the graph given in above fugure

intV = 5;

structGraph*
graph = createGraph(V);

addEdge(graph,
0, 1);

addEdge(graph,
0, 4);

addEdge(graph,
1, 2);

addEdge(graph,
1, 3);

addEdge(graph,
1, 4);

addEdge(graph,
2, 3);

addEdge(graph,
3, 4);

//print the adjacency list representation of the above graph

printGraph(graph);

return0;

}

Output:

Adjacency list of vertex 0

head
-> 4-> 1

Adjacency
list of vertex 1

head
-> 4-> 3-> 2-> 0

Adjacency
list of vertex 2

head
-> 3-> 1

Adjacency
list of vertex 3

head
-> 4-> 2-> 1

Adjacency
list of vertex 4

head
-> 3-> 1-> 0

Pros:
Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of
edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.

Cons: Queries like whether there is an edge from
vertex u to vertex v are not efficient and can be done O(V).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Non-Linear Data Structures : Graph and its representations - Tree |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.