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

Page Contents

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

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

1. Depth-first search (DFS)

#### 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)```

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