Graph in data structure is another most important concept in data structure.

In this tutorial we will see what is graph in data structure, Graph definition, types of graphs and graph traversal techniques.

**What is graph in data structure ?**

**Graph definition in data structure :**

A graph is a set of vertices (v) bad set of edges (E). The set v is a finite , non empty set of vertices.

The set E is a set of pair of vertices representing edges.

G = (v,E)

V (G) = vertices of graph G

E (G) = edges of graph G

**Graph representation in data structure**

consider above graph

**Graph example**

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

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

A graph is said to be connected if there exists a path between every pair of vertices Vi and Vj.

**Types of graph in data structure**

The graph may be directed or undirected.

**1. Directed graph in data structure**

A directed graph is graph that is set of edges and nodes connected to each other, All edges are directed from one vertex to another is called as directed graph.

**2. Undirected graph in data structure**

A directed graph is graph that is set of edges and nodes connected to each other. their is no direction to any vertex is undirected graph.

**Representation of graph**

**1. Matrix representation :**

A two dimensional matrix can be used to store a graph. A graph G (V,E) where v={0,1,2…} can be represented using two dimensional array of size N×N.

A graph is represented using a square matrix.

**2. Link representation**

A graph can be represented using a linked list.

For vertex, a list of adjacent vertices in maintained using a linked list.

It creates a separate linked list for each vertex Vi in graph G (V,E).

**Graph traversal in data structure**

Lets see graph traversal methods in data structure

Represent graph and traverse it using DFS and BFS

- Depth first search (DFS)
- Breadth first search (BFS)

**Depth first search (DFS)**

It is like pre order Traversal of a tree. Traversal can start from any vertex,say Vi. Vi is visited and then all vertices adjacent to Vi are traversed recursively using DFS.

**DFS graph algorithm**

for each vertex V

do flag[V] = false

Recursivedfs (s)

Algorithm for Recursivedfs (v)

Flag [V] = true

For each neighbours w of v

do if flag(w) =false

then Recursivedfs (w)

**Breadth first search (BFS)**

It is another popular approach used for visit the vertices of a graph.

This method starts from a given vertex V0.V0 is marked as visited. All vertices adjacent to V0 are visited next.

The method continues until all vertices are visited .

The algorithm for BFS has to maintain a list of vertices which have been visited but bit explored for adjacent vertices.

**Algorithm for BFS**

BFS(s)

Input : s is source vertex

Output : mark all vertices that can be visited.

For each vertex V.

do flag [V] = false

Q = empty queue

flag [s] = true

Enqueue (Q,s)

While Q is not empty

do V= dequeue (Q)

for each U adjacent to v

do if flag [w] = false

then flag[w] = true

Enqueue(Q,s)

**Graph traversal example**

Let see example for traversing graph using graph traversal technique

**BFS example**

Traverse the graph using BFS technique

BFS sequence = A | B C D E | F G | H

**DFS example**

Traverse the graph using DFS technique

DFS sequence

DFS(G,1) is,

Visit(1)

Next visit nodes adjacent to 1

DFS(G,2)

DFS(G,3)

DFS(G,4)

DFS(G,5)

## Leave a Reply