0
9.1kviews
What is graph? Explain methods to represent graph
0
432views
1. Graph is a non-linear data structure that is same as the mathematical (discrete mathematics) concept of graphs.
2. It is a collection of nodes (also called as vertices) and edges that connect these vertices.
3. Graphs are used to represent arbitrary relationship among objects.
4. A graph can be directed or undirected.
5. Consider the graph

G= (V, E)

V (G) = Vertices of Graph G

E (G) = Edges of Graph G

then,

V(G)={A,B,C,D,E,F}

E(G)={(AB),(AC),(BD),(BC),(DE),(DF),(EF)}

1. Graphs can be represented in two forms

a. Sequential Representation


2. Sequential Representation

1.Graphs can be represented through matrix in systems memory.

2.This is sequential in nature.

3.This type of representation is called sequential representation of graphs

4.Following are the types of sequential representation of graphs

a.Adjacent matrix representation

b.Path matrix representation


   a.The Adjacency matrix of a graph G with n vertices is N x N.

b.It is given by A=[aij].
aij=1 if ith and jth   vertices are adjacent.
=0 if ith and jth vertices are not adjacent.
c.Example


1. A graph can be represented using a linked list.

2. It requires less amount of memory.

3. For each vertex, a list of adjacent vertices is maintained using a linked list.

4. Adjacency list of a graph is represented by an array of pointers and each pointer points to the respected linked list of vertex.

5. Example Consider the diagram

Adjacency list of a graph as shown below