Graph Data structure
By
Dr. Anita Murmu
Graph
• A graph is a non-linear data structure made up of vertices (nodes) and
edges (connections) that represent relationships between objects. Unlike
arrays or linked lists, graphs do not follow a sequential order.
• Example: On a map, each city is a vertex, and each road connecting two
cities is an edge. This way, a graph represents how cities are linked.
Components of a Graph Data
Structure
A graph is a collection of objects where
some pairs of objects are connected. It
consists of the following components: 2. Edge (Link/Connection)
An edge is the link connecting two
1. Vertex (Node) vertices.
A vertex is a fundamental unit of the
graph. It represents:
•Road between two cities
It represents: •Cable between computers
• A city in a map •Relationship between people
• A computer in a network
• A person in a social network
• A task in a project
Types Of Graphs in Data Structure and Algorithms
• A graph can be divided into multiple categories based on different properties such
as edges, direction, connectivity and many others.
Based on weight :
1. Weighted Graphs
A weighted graph is a graph where each edge has a number (weight) that represents distance, cost, or
time.
2. Unweighted Graphs
An unweighted graph is a graph where all edges are treated equally, with no extra values like distance or
cost.
Based on Edge Direction:
3. Undirected Graph::: A graph in which edges do not have any direction. That is the nodes are unordered pairs
in the definition of every edge.
4. Directed Graph::: A graph in which edge has direction. That is the nodes are ordered pairs in the definition of
every edge.
Representation of Graph Data Structure:
There are multiple ways to store a graph: The following are the most common
representations.
•Adjacency Matrix
•Adjacency List
Adjacency Matrix Representation of Graph Data Structure:
In this method, the graph is stored in the form of the 2D matrix where
rows and columns denote vertices. Each entry in the matrix represents
the weight of the edge between those vertices.
matrix[i][j] = 1 if there is an edge between vertex i and vertex j.
matrix[i][j] = 0 if there is no edge.
Adjacency List Representation of Graph:
This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges
connected to that vertex.
Feature Adjacency Matrix Adjacency List
2D matrix where each cell (i, j) shows List (array of linked lists/vectors)
Definition
whether an edge exists where each node stores its neighbors
O(V²) (always large, even for few
Space Required O(V + E) (efficient, depends on edges)
edges)
Best For Dense graphs (many edges) Sparse graphs (few edges)
Memory Usage High Low
Good for all types; especially dynamic
Graph Type Support Good for weighted & unweighted
graphs
Traversal Slower (must check all columns) Faster (only visit neighbors)
Matrix Form Fixed-size V×V table Dynamic list per node
Traversal Technique of Graph
Traversal techniques are used to visit all the vertices of a graph systematically. These
methods help to explore the graph completely and are useful for solving many graph-related
problems.
1. Depth First Search (DFS):
•Explores as far as possible along each branch before backtracking.
•Uses a stack (or recursion).
2. Breadth First Search (BFS)
•Explores all neighbors of a vertex before moving to the next level.
•Uses a queue.
DFS. void addEdge(int adj[V][V], int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1; // undirected
#include <stdio.h> }
#define V 5 int main() {
int adj[V][V] = {0};
void dfsRec(int adj[V][V], int visited[V], int s, int res[V], int *idx) {
visited[s] = 1;
res[(*idx)++] = s; // creating adjacency list
addEdge(adj, 1, 2);
// Recursively visit all adjacent vertices addEdge(adj, 1, 0);
// that are not visited yet addEdge(adj, 2, 0);
for (int i = 0; i < V; i++) { addEdge(adj, 2, 3);
if (adj[s][i] && visited[i] == 0) addEdge(adj, 2, 4);
dfsRec(adj, visited, i, res, idx);
} int res[V];
}
// Perform DFS starting from the source vertex 0
void dfs(int adj[V][V], int res[V]) { dfs(adj, res);
int visited[V] = {0};
int idx = 0; for (int i = 0; i < V; i++)
dfsRec(adj, visited, 0, res, &idx); printf("%d ", res[i]);
}
return 0;
}
BFS.
#include <stdio.h>
void addEdge(int adj[V][V], int u, int v) {
#define V 5
#define MAXQ 100 adj[u][v] = 1;
adj[v][u] = 1; // undirected
// BFS for single connected component }
void bfs(int adj[V][V], int res[V], int *resSize) {
int main() {
int visited[V] = {0};
int q[MAXQ]; int adj[V][V] = {0};
int front = 0, rear = 0;
int src = 0;
visited[src] = 1; // creating adjacency list
addEdge(adj, 1, 2);
q[rear++] = src;
addEdge(adj, 1, 0);
addEdge(adj, 2, 0);
while (front < rear) {
int curr = q[front++]; addEdge(adj, 2, 3);
res[(*resSize)++] = curr; addEdge(adj, 2, 4);
// visit all the unvisited int res[V];
int resSize = 0;
// neighbours of current node
for (int x = 0; x < V; x++) {
if (adj[curr][x] && !visited[x]) { bfs(adj, res, &resSize);
visited[x] = 1;
q[rear++] = x; for (int i = 0; i < resSize; i++)
printf("%d ", res[i]);
}
}
} return 0;
}
}
BFS DFS
1. Breadth First Search 1. Depth First Search
2. 2. BFS traverses the tree level wise. 2. DFS traverses tree depth wise
3. Use Queue data structure. 3. Use Stack data structure
4. It works on FIFO 4. It works in LIFO
5. Requires more memory as compared to DFS 5. DFS requires less memory as compared to BFS
6. It always provides the shallowest path solution. 6. Does not guarantee show lest path solution.
7. No backtracking is required in BFS. 7. Backtracking is implemented in DFS
1
BFS: 1 2 3 4 7 5 6
1, 2, 3, 4, 7, 5, 6 3
2
7
DFS: 4
1, 2, 4, 5, 6, 3, 7
3
44 4 5 6
2
1
Hashing in Data Structure
• Hashing is a technique used in data structures that efficiently stores and retrieves data
in a way that allows for quick access.
• Hashing involves mapping data to a specific index in a hash table (an array of items)
using a hash function. It enables fast retrieval of information based on its key.
• The great thing about hashing is, we can achieve all three operations (search, insert and
delete) in O(1) time on average.
• Hashing is mainly used to implement a set of distinct items (only keys) and dictionaries
(key value pairs).
• Collision Resolution Techniques
1. Chaining (open Hashing) also known as quadratic probing
2. Open Addressing (close Hashing) also known as linear probing
Draw Binary tree
((a + (b – c)) * (d + e * f))
• The root is * because the whole expression
is one multiplication.
• The left subtree is (a + (b - c))
• The right subtree is (d + e * f)
• In (b - c), - becomes the parent of b and c.
• In (e * f), * becomes the parent of e and f.