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
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
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,
Visit(1)
Next visit nodes adjacent to 1
DFS(G,2)
DFS(G,3)
DFS(G,4)
DFS(G,5)

Write A Comment