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 in Data structure
Graph in 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

  1. Depth-first search (DFS)
  2. 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
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

Graph traversal example

Let see the example for traversing the graph using graph traversal technique

BFS example
BFS example
BFS example

Traverse the graph using BFS technique
BFS sequence = A | B C D E | F G | H

DFS example

DFS example
DFS example

Traverse the graph using DFS technique
DFS sequence
DFS(G,1) is,
Next visit nodes adjacent to 1

Write A Comment