Page 275 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Graph depicted in Figure 13.9 is a tree and so are the ones depicted in Figure 13.10(a) to
13.10(e).
Figure 13.10: Tree Structure

1
A
2 3
B

C 4 5 6 7
A
D
8 9 10
E
(a) (b) (c)

1
1
3
2
7

3 6
4 8
(d) (e)

Because of their special structure and properties, trees occur in many different applications in
computer science.
?
Did u know? In Figure 13.8 how many outdegree present in vertex 4.

13.3 Representations of Graphs

Graph is a mathematical structure and finds its application in many areas of interest in which

problems need to be solved using computers. Thus, this mathematical structure must be
represented as some kind of data structures. Two such representations are, commonly used.
These are:
1. Adjacent Matrix

2. Adjacency List representation.
The choice of representation depends on the application and function to be performed on the
graph.

13.3.1 Adjacent Matrix

The adjacency matrix A for a graph G = (V,E) with n vertices, is an n × n matrix of bits, such
that A
A = 1, iff there is an edge from v to v and
ij i j
A = 0, if there is no such edge.
ij

270 LOVELY PROFESSIONAL UNIVERSITY