Graphs in Data Structure

Table of Contents

What is a Graph?

A graph is a pair G ={V,E} where‘ V’ is a set of vertices and ‘E’ is a set of edges between the vertices.

V = {a,b,c,d}

E = { (a, b), (b. c), (c. d), (d, a),(b, d)}

Degree of vertex : No. of edges join with that vertex if a vertex has no edge associated with its degree is 0.

Path: A sequence of vertices traversed by following the edges between them.

Cycle: It is a path that includes the same vertex 2 or more times.

Sparse Graph: Number of edges is less than equal to number of vertices.

Dense Graph: Number of edges greater than number of vertices.

A directed graph ‘G’ is a pair {V,E} where ‘V’ is a set of vertices and ‘E’ is a set of ordered pairs of vertices.

A Undirected Graph ‘G’ is a pair {V,E} where ‘V’ is a set of vertices and ‘E’ is a set of unordered pair of vertices .

A graph which has value associated with each edge this can be a distance cost or some other numeric value associated with the edge.

A graph in which there is only one edge between two vertices are called simple Graph.

This representation is suitable for sparse graph.

The adjacency list representation

This is Suitable For Dense Graph

The adjacency matrix representation of a Graph G ={V,E} consist of |V| x |V| matrix A { A =$a_{ij}$ }

Such that

$a_{ij}=\begin{bmatrix}
0 & if (i,j)\varepsilon E\\
1 & otherwise
\end{bmatrix}$