Graphs

GRAPH

A graph G consists of a set of V vertices and a set of E edges.

G = ( V , E )

Tree – A graph is a tree if it has two properties:

• It is connected
• There are no cycles in the graph

Graph representation

Commonly used representations are:

1. 1. Adjacency matrix

Aij =  1 ; if edge (Vi,Vj) is in Eg

0 ; otherwise

=> It takes O(n²) space to represent a graph with n vertices

=> It takes O(n²) time to solve most of graph problem

1. 2. Adjacency list representation

We store graph as a linked list

1. 3. Multi-list representation

In it there are two parts, a directory of node information and a set of linked list of edge information.

Graph Traversal

Breadth-first Traversal

Depth First Traversal`c