Data Structures Using C, 2nd Edition by Pearson

Graphs 373

In case of weighted graphs, the weight is also included with the edge information making it a 3-tuple,

i.e., (w, vi, vj) where w is the weight of edge between vertices vi and vj. The set representation for a

weighted graph is given in Figure 8.15.

Note: If in a graph G, there are N vertices and M edges, the adjacency matrix has space complexity O(N

2

)

and that of adjacency list is O(M).

8.3.3 Set Representation of Graphs

This representation follows the definition of the graph itself in the sense that it maintains two sets: V- ‘Set

of Vertices’ and E-‘Set of Edges’. The set representation for various graphs is given in Figure 8.14.