**The Graph in Data structure** is another most important concept in the data structure.

## Graph in Data Structure

Graph is Non-linear data structure which contains a collection of nodes and edges.

**What is a graph in data structure?**

**Graph definition in Data structure:** A graph is a pictorial representation of a set of nodes where nodes are connected by links.

The Nodes are referred to as vertices and the links between nodes are referred to as arcs or edges.

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

The graph Data structure is also used to represent Network.

### Graph representation in the data structure

### Graph example

Consider above graph

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. The directed graph in Data structure

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

#### 2. The undirected graph in Data structure

A directed graph is a graph that is set of edges and nodes connected to each other. there is no direction to any vertex is an 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 a 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 is 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

Let’s see graph traversal methods in the data structure

Represent graph and traverse it using DFS and BFS

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

#### 1. 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)

#### 2. Breadth-first search (BFS)

It is another popular approach used to 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 the example for traversing the 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)