Unit - 5

Graph and Hashing

Prepared By:
Ms. Purvi Tandel, Chandni Naik
 Topics of Unit 5
• Graph-Definitions and Concepts
• Matrix and list representation of graphs
• Elementary graph operations - Breadth first search
• Elementary graph operations - Depth first search
• Hashing - Hashing functions
• Collision-Resolution techniques.
Introduction of Graph
• Graph is a non-linear data structure.
• It contains a set of points known as nodes (or vertices) and a set of links
known as edges (or Arcs).
• Here edges are used to connect the vertices. 
• Generally, a graph G is represented as G = ( V , E ), where V is set of
vertices and E is set of edges.
Example:
• Graph with 5 vertices and 6 edges.
This graph G can be defined as G = ( V , E )
Where V = {A,B,C,D,E} and
E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

Graph is a collection of nodes and edges in which nodes are connected with edges.
Graph Definitions
1) Graph: A graph G is defined as an ordered set (V, E), where V(G) represents
the set of vertices and E(G) represents the edges that connect these
vertices.
2) Vertex: Individual data element of a graph is called as Vertex. Vertex is also
known as node.
3) Edge: An edge is a connecting link between two vertices. Edge is also known
as Arc.
Graph Definitions
4) Adjacent Node: For every edge, e = 5) Directed graph: In a directed
(u, v) that connects nodes u and v, the graph, edges form an ordered pair. If
nodes u and v are the end-points and there is an edge from A to B, then
are said to be the adjacent nodes or there is a path from A to B but not
neighbors. from B to A.
In example A and B are adjacent The edge (A, B) is said to initiate
nodes. from node A (also known as initial
node) and terminate at node B
(terminal node).
Graph Definitions
6) Undirected Graph: In an undirected 7) Loop: An edge that has identical
graph, edges do not have any end-points is called a loop.
direction associated with them. That That is, e = (u, u).
is, if an edge is drawn between nodes
A and B, then the nodes can be
traversed from A to B as well as from
B to A.
Graph Definitions
8) Parallel Edge: In some directed as 9) Distinct Edge: In case of directed
well as undirected graphs, we may edges, two possible edges between
have certain pairs of nodes joined by any pair of nodes which are opposite
more than one edges, such edges are in direction are considered Distinct.
called Parallel edges. In example edges between node 2
In example edges between node 1 and 3 are distinct edges.
and 2 are parallel edges. 2

2 2
1 2 2
2
2 1
1 3 1 3

1 1 1 1
4 4
Graph Definitions
10) Weighted Graph: In a weighted 11) Isolated Graph: In a graph a
graph, the edges of the graph are node which is not adjacent to any
assigned some weight or length. The other node is called isolated node.
weight of an edge denoted by w(e) is
a positive value which indicates the
cost of traversing the edge.
Graph Definitions
12) Null Graph: A graph having no edges is called a Null Graph.
A graph containing only isolated nodes are called null graph.

13) Degree of node: The degree of a node, written as deg(u), is equal to the
sum of in-degree and out-degree of that node.
degree(u) = indegree(u) + outdegree(u)

Indegree : The no of edges which have V as their terminal node is call as indegree of node V.
Outdegree : The no of edges which have V as their initial node is call as outdegree of node V.
Degree of A = 2, Degree of B = 3
Degree of C = 2, Degree of D = 3
Degree of E = 2
Matrix and list representation of graphs
Graph data structure is represented using following representations.

• Adjacency Matrix
• Adjacency List (Linked List)
 Matrix and list representation of graphs
Graph data structure is represented using following representations.
1) Adjacency Matrix: In this representation, the graph is represented using a matrix of
size total number of vertices by a total number of vertices. That means a graph with 4
vertices is represented using a matrix of size 4X4. In this matrix, both rows and columns
represent vertices. This matrix is filled with either 1 or 0. Here, 1 represents that there is
an edge from row vertex to column vertex and 0 represents that there is no edge from
row vertex to column vertex.

Undirected
graph
representation
Matrix and list representation of graphs
Graph data structure is represented using following representations.
1) Adjacency Matrix: In this representation, the graph is represented using a matrix of
size total number of vertices by a total number of vertices. That means a graph with 4
vertices is represented using a matrix of size 4X4. In this matrix, both rows and columns
represent vertices. This matrix is filled with either 1 or 0. Here, 1 represents that there is
an edge from row vertex to column vertex and 0 represents that there is no edge from
row vertex to column vertex.

Directed graph
representation
Matrix and list representation of graphs
Graph data structure is represented using following representations.
1) Adjacency Matrix: One more example in directed graph representation.

For a given graph G =m (V, E), an adjacency matrix depends upon the ordering of the
elements of V.

V1 V4 V1 V2 V3 V4
V1 0 1 0 1
A = V2 1 0 0 0
V3 1 1 0 1
V4 0 1 0 0
V2 V3
Matrix and list representation of graphs
Graph data structure is represented using following representations.
2) Adjacency List: In this representation, every vertex of graph contains list of its adjacent
vertices.
For example, consider the following directed graph representation implemented using
linked list.
Matrix and list representation of graphs
Graph data structure is represented using following representations.
2) Adjacency List: One more example of undirected graph representation.
0

4
1
2

0 1 2 3 4
1 0 3
2 0 3 4
3 0 1 2 4
4 0 2 3
Elementary graph operations – DFS & BFS
• One of the elementary operation on graph is graph traversal.
• Graph traversal is technique used for searching a vertex in a graph.
• The graph traversal is also used to decide the order of vertices to be visit in the
search process.
• A graph traversal finds the edges to be used in the search process without
creating loops that means using graph traversal we visit all vertices of graph
without getting into looping path.

There are two graph traversal techniques:

• DFS (Depth First Search)
• BFS (Breadth First Search)
DFS – Depth First Search
Depth First Search (DFS) algorithm traverses a graph in a depth-ward motion and
uses a stack to remember to get the next vertex to start a search, when a dead
end occurs in any iteration.

✓ A

✓ B C✓
✓ D ✓ E F ✓ G ✓

H
✓
ABDHECFG
 DFS – Depth First Search
We use the following steps to implement DFS traversal.
1) Define a Stack of size total number of vertices in the graph.
2) Select any vertex as starting point for traversal. Visit that vertex and push it on
to the Stack.
3) Visit any one of the adjacent vertex of the vertex which is at top of the stack
which is not visited and push it on to the stack.
4) Repeat step 3 until there are no new vertex to be visit from the vertex on top
of the stack.
5) When there is no new vertex to be visit then use back tracking and pop one
vertex from the stack.
6) Repeat steps 3, 4 and 5 until stack becomes Empty.
7) When stack becomes Empty, then produce final spanning tree by removing
unused edges from the graph.
DFS – Depth First Search – Example 1
1 Initialize the stack.

2
Mark S as visited and put it onto the stack. Explore any
unvisited adjacent node from S. We have three nodes and
we can pick any of them. For this example, we shall take
the node in an alphabetical order.

Mark A as visited and put it onto the stack. Explore any

unvisited adjacent node from A. Both S and D are adjacent
to A but we are concerned for unvisited nodes only.
DFS – Depth First Search – Example 1
4 Visit D and mark it as visited and put onto the
stack. Here, we have B and C nodes, which are
adjacent to D and both are unvisited. However,
we shall again choose in an alphabetical order.

5
We choose B, mark it as visited and put onto the stack.
Here B does not have any unvisited adjacent node. So, we
pop B from the stack.

We check the stack top for return to the previous

node and check if it has any unvisited nodes. Here,
we find D to be on the top of the stack.
DFS – Depth First Search – Example 1
7
Only unvisited adjacent node is from D is C now.
So we visit C, mark it as visited and put it onto
the stack.

For DFS sequence, write the vertex in order of

their visited sequence.

Answer:
DFS sequence (visited sequence): S A D B C
Spanning tree:

A spanning tree of a connected, undirected graph G

is a sub-graph of G which is a tree that connects all
the vertices together.
Resulted spanning tree
Introduction to Minimum spanning tree
Spanning Tree:
• A spanning tree of a connected, undirected graph G is a sub-graph of G which is a tree that
connects all the vertices together.
• A graph G can have many different spanning trees. We can assign weights to each edge
(which is a number that represents how unfavorable the edge is), and use it to assign a
weight to a spanning tree by calculating the sum of the weights of the edges in that
spanning tree.
Introduction to Minimum spanning tree
Minimum spanning tree:
• A minimum spanning tree (MST) is defined as a spanning tree with weight less than or
equal to the weight of every other spanning tree.

• In other words, a minimum spanning tree is a spanning tree that has weights associated
with its edges, and the total weight of the tree (the sum of the weights of its edges) is at a
minimum.
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
A
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABC
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABCED
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABCEDF
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABCEDFG
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABCEDFG
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABCEDFG
DFS – Depth First Search – Example 2
Answer:

DFS sequence
(visited sequence):
ABCEDFG
DFS – Depth First Search – Exercise
Question
Find the sequence of traverse using DFS.
a. Starting point is A
Answer:

b. Starting point is H Starting Vertex A:

ABEFCGIHD

Starting Vertex H:
HEFCBGI (A and D are
unreachable)
BFS – Breadth First Search
Breadth First Search (BFS) algorithm traverses a graph in a breadth-ward motion
and uses a queue to remember to get the next vertex to start a search, when a
dead end occurs in any iteration.

✓
A
✓ B ✓ C
✓
✓ D ✓ E F✓ G

H✓
A | B C| D E F G | H
 BFS – Breadth First Search
We use the following steps to implement BFS traversal.
1) Define a Queue of size total number of vertices in the graph.
2) Select any vertex as starting point for traversal. Visit that vertex and insert it
into the Queue.
3) Visit all the adjacent vertices of the vertex which is at front of the Queue
which is not visited and insert them into the Queue.
4) When there is no new vertex to be visit from the vertex at front of the Queue
then delete that vertex from the Queue.
5) Repeat step 3 and 4 until queue becomes empty.
6) When queue becomes Empty, then produce final spanning tree by removing
unused edges from the graph.
BFS – Breadth First Search – Example 1
1 Initialize the queue.

2
We start from visiting S (starting node), and mark
it as visited.

3
We then see an unvisited adjacent node from S.
In this example, we have three nodes but
alphabetically we choose A, mark it as visited
and enqueue it.
BFS – Breadth First Search – Example 1
4 Next, the unvisited adjacent node
from S is B. We mark it as visited and
enqueue it.

5
Next, the unvisited adjacent node from S is C.
We mark it as visited and enqueue it.

Now, S is left with no unvisited adjacent

nodes. So, we dequeue and find A.
BFS – Breadth First Search – Example 1
7
From A we have D as unvisited adjacent
node. We mark it as visited and
enqueue it.

For BFS sequence, write the vertex in

order of their visited sequence.

Answer:
BFS sequence (visited sequence): S A B C D
Spanning tree:

A spanning tree of a connected, undirected graph G

is a sub-graph of G which is a tree that connects all
the vertices together.
Resulted spanning tree
BFS – Breadth First Search – Example 2
Answer:

BFS sequence
(visited sequence):
A
BFS – Breadth First Search – Example 2
Answer:

BFS sequence
(visited sequence):
ADEB
BFS – Breadth First Search – Example 2
Answer:

BFS sequence
(visited sequence):
ADEBCF
BFS – Breadth First Search – Example 2
Answer:

BFS sequence
(visited sequence):
ADEBCFG
BFS – Breadth First Search – Example 2
Answer:

BFS sequence
(visited sequence):
ADEBCFG
BFS – Breadth First Search – Exercise
Question
Find the sequence of traverse using BFS.
a. Starting point is A
Answer:

b. Starting point is H Starting Vertex A:

ABCDEGFIH

Starting Vertex H:
HEICFBG (A and D are
unreachable)
Differentiate DFS and BFS
DFS BFS
• DFS stands for Depth First Search. • BFS stands for Breadth First Search.

• DFS starts the traversal from the • BFS starts traversal from the root
root node and explore the search as node and then explore the search
far as possible from the root node. level by level. i.e. as close as
i.e. depthwise possible from root node

• DFS can be done using stack (LIFO • BFS can be done using queue (FIFO
implementation) implementation)
Differentiate DFS and BFS
DFS BFS
Example: Example:
Thank you