DATA STRUCTURE

AND
ALGORITHM

Dr. Irfana Memon

Department of CSE, QUEST

1
https://sites.google.com/a/quest.edu.pk/dr-irfana-memon/lecture-slides
 Course Content
NO TOPIC CLO
01 A General Overview CLO1
02 Introduction to Data Structures and Algorithm CLO1
03 String Processing CLO1
04 Abstract Data Types CLO1
05 Linked list CLO1
06 Stack and Queue CLO1
07 Recursion CLO1
08 Complexity Analysis CLO2
09 Sorting and Searching techniques CLO2
10 Trees CLO2
11 Graph CLO3
12 P & NP CLO3

2
 What is a 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.
• A graph is defined as follows...
 Graph is a collection of vertices and arcs in which vertices are
connected with arcs
 (OR) Graph is a collection nodes and edges arcs in which
nodes are connected with edges

3
 What is a graph?
Generally, a graph G is represented as G = ( V , E ), where V is set of
vertices and E is set of edges.

Example
The following is a 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)}.

4
 Graph Terminology
• We use the following terms in graph data structure...

Vertex
Individual data element of a graph is called as Vertex.
Vertex is also known as node.

Edge
An edge is a connecting link between two vertices.
Edge is also known as Arc.
An edge is represented as (startingVertex, endingVertex).

5
 Graph Terminology
Edge types:
Undirected Edge -
An undirected egde is a bidirectional edge.
If there is undirected edge between vertices A and B then edge
(A , B) is equal to edge (B , A).

Directed Edge -
A directed egde is a unidirectional edge.
If there is directed edge between vertices A and B then edge (A ,
B) is not equal to edge (B , A).

Weighted Edge -
A weighted egde is a edge with value (cost) on it. 6
 Graph Terminology

Types of Graph:

Undirected Graph
A graph with only undirected edges is said to be undirected graph.

Directed Graph
A graph with only directed edges is said to be directed graph.

Mixed Graph
A graph with both undirected and directed edges is said to be mixed
graph.
7
 Graph Terminology
End vertices or Endpoints
The two vertices joined by edge are called end vertices (or
endpoints) of that edge.

Origin
If a edge is directed, its first endpoint is said to be the origin of it.

Destination
If a edge is directed, its first endpoint is said to be the origin of it and
the other endpoint is said to be the destination of that edge.

Adjacent
If there is an edge between vertices A and B then both A and B are
said to be adjacent. In other words, vertices A and B are said to be
adjacent if there is an edge between them. 8
 Graph Terminology
Incident
Edge is said to be incident on a vertex if the vertex is one of the
endpoints of that edge.

Outgoing Edge
A directed edge is said to be outgoing edge on its origin vertex.

Incoming Edge
A directed edge is said to be incoming edge on its destination vertex.

Degree
Total number of edges connected to a vertex is said to be degree of
that vertex.
9
 Graph Terminology
Indegree
Total number of incoming edges connected to a vertex is said to be
indegree of that vertex.

Outdegree
Total number of outgoing edges connected to a vertex is said to be
outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges with same end vertices and two
directed edges with same origin and destination, such edges are
called parallel edges or multiple edges.

10
 Graph Terminology
Self-loop
Edge (undirected or directed) is a self-loop if its two endpoints
coincide with each other.

Simple Graph
A graph is said to be simple if there are no parallel and self-loop
edges.

Path
A path is a sequence of alternate vertices and edges that starts at a
vertex and ends at other vertex such that each edge is incident to its
predecessor and successor vertex.

11
 Graph Representation
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.

12
 Graph Representation
Graph data structure is represented using following
representations...
1. Adjacency Matrix
2. Incidence Matrix
3. Adjacency List

13
 Graph Representation
Adjacency Matrix
For example, consider the following undirected graph representation…

14
 Graph Representation
Adjacency Matrix
For example, consider the following directed graph representation…

15
 Graph Representation
Incidence Matrix

• In this representation, the graph is represented using a matrix of

size total number of vertices by a total number of edges.
• That means graph with 4 vertices and 6 edges is represented
using a matrix of size 4X6.
• In this matrix, rows represent vertices and columns represents
edges.
• This matrix is filled with 0 or 1 or -1.
• Here, 0 represents that the row edge is not connected to column
vertex, 1 represents that the row edge is connected as the outgoing
edge to column vertex and -1 represents that the row edge is
connected as the incoming edge to column vertex.
16
 Graph Representation
Incidence Matrix

• For example, consider the following directed graph representation...

17
 Graph Representation
Adjacency List
In this representation, every vertex of a graph contains list of its adjacent
vertices.
For example, consider the following directed graph representation
implemented using linked list...

18
 Graph Representation
Adjacency List
For example, consider the following directed graph representation
implemented using an array as follows..

19
 Graph Traversal
• Graph traversal is a technique used for a searching vertex in a
graph.
• The graph traversal is also used to decide the order of vertices is
visited 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 the vertices of the
graph without getting into looping path.

• There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)
2. BFS (Breadth First Search)

20
 Depth First Search (DFS)
• DFS traversal of a graph produces a spanning tree as final result.
• Spanning Tree is a graph without loops.
• We use Stack data structure with maximum size of total number of
vertices in the graph to implement DFS traversal.

21
 Depth First Search (DFS)
• We use the following steps to implement DFS traversal...

Step 1 - Define a Stack of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it
on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the
top of stack and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which
is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one
vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing
unused edges from the graph

Back tracking is coming back to the vertex from which we reached the current
22
vertex.
 Depth First Search (DFS)
EXAMPLE:

23
 Depth First Search (DFS)
EXAMPLE:

24
 Depth First Search (DFS)
EXAMPLE:

25
 Depth First Search (DFS)
EXAMPLE:

26
 Depth First Search (DFS)
EXAMPLE:

27
 Depth First Search (DFS)
EXAMPLE:

28
 Depth First Search (DFS)
EXAMPLE:

29
 Depth First Search (DFS)
EXAMPLE:

30
 Depth First Search (DFS)
EXAMPLE:

31
 Depth First Search (DFS)
EXAMPLE:

32
 Depth First Search (DFS)
EXAMPLE:

33
 Depth First Search (DFS)
EXAMPLE:

34
 Depth First Search (DFS)
EXAMPLE:

35
 Depth First Search (DFS)
EXAMPLE:

36
 Depth First Search (DFS)
EXAMPLE:

37
 Depth First Search (DFS)
EXAMPLE:

38
 Breadth First Search (BFS)
• BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a
graph without loops.
•We use Queue data structure with maximum size of total number of vertices in the graph
to implement BFS traversal.

We use the following steps to implement BFS traversal...

Step 1 - Define a Queue of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into
the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the
Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front of the
Queue then delete that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing unused
edges from the graph

39
 Breadth First Search (BFS)
EXAMPLE:

40
 Breadth First Search (BFS)
EXAMPLE:

41
 Breadth First Search (BFS)
EXAMPLE:

42
 Breadth First Search (BFS)
EXAMPLE:

43
 Breadth First Search (BFS)
EXAMPLE:

44
 Breadth First Search (BFS)
EXAMPLE:

45
 Breadth First Search (BFS)
EXAMPLE:

46
 Breadth First Search (BFS)
EXAMPLE:

47
 Breadth First Search (BFS)
EXAMPLE:

48
 Breadth First Search (BFS)
EXAMPLE:

49
 Wish
You
Good Luck
50