Jimma University

Faculty of Computing and Informatics

Software Engineering

Chapter Seven:
Graph

Jimma, Ethiopia.
 Objective

 At the end of the session students should have a basic understanding of

 Graph: Definition, Terminologies,
 Graph Representations
 Traversing a Graph

2
 Introduction

 In data structures, a graph is a non-linear data structure that consists of a collection of

nodes (also called vertices) and edges that connect pairs of nodes.
 Graphs are a fundamental concept in computer science and are widely used in various
algorithms, data structures, and applications to model and analyze complex
relationships and networks.
 Graphs are widely used to represent relationships or connections between entities in
various domains, such as computer networks, social networks, transportation
systems, and organizational structures.
 Understanding graphs and their properties is essential for solving a wide range of
problems in fields such as network analysis, route planning, social network
analysis, and computational biology.
3
 Graph

 Graph is a collection of vertices and arcs which connects vertices in the 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
 Cont...

 Consider a graph, G

 Then the vertex V and edge E can be represented as:

 V = {v1, v2, v3, v4, v5, v6} and
 E = {e1, e2, e3, e4, e5, e6} E = {(v1, v2) (v2, v3) (v1, v3) (v3, v4), (v3, v5) (v5, v6)}.
There are six edges and vertex in the graph

5
 Definitions and Representation

• An undirected graph
• G is a pair (V, E), where V is a finite set of points called vertices and E is a finite
set of edges.
• An edge e ∈ E is an unordered pair (u,v), where u,v ∈ V. Edges have no
direction associated with them, meaning that the relationship between
nodes is bidirectional.
• An undirected graph can be represented geometrically as a set of marked
points (called vertices) V with a set of lines (called edges) E between the
points.

6
 Cont...

 In a directed graph,
 the edge e is an ordered pair (u,v). An edge (u,v) is incident from vertex u and is
incident to vertex v.
 A directed graph can be represented geometrically as a set of marked points
(called vertices) V with a set of arrows (called edges) E between pairs of points
(or vertex or nodes) so that there is at most one arrow from one vertex to
another vertex.
Each edge has a direction associated with it, indicating that the relationship
between nodes is one-way.
 The length of a path is defined as the number of edges in the path.
 Note: A directed graph is also called a digraph and an undirected graph is also
known as a graph.
7
 Definitions and Representation

a) An undirected graph and (b) a directed graph.

8
 Terminologies V
a b
h j
 End vertices (or endpoints) of an edge
U d X Z
 U and V are the endpoints of a
 Edges incident on a vertex c e i
 a, d, and b are incidents on V W g
 Adjacent vertices
 Two vertices are said to be adjacent f

if they are joined by an edge.

Y

 U and V are adjacent

 Degree of a vertex (no. of adjacent vertices or no. edges incident to that vertices)
 X has a degree of 5
 Parallel edges: h and i are parallel edges
 Self-loop: The starting and ending point of an edge will be the same: j is a self-loop
 A sub-graph of G is said to be a spanning sub-graph if it contains all the vertices of G.
 A vertex is said to be an isolated vertex if there is no edge incident with it. If the degree of vertex a is zero, then vertex a
9 is called isolated vertex
 Terminologies (cont.)
 Path: sequence of alternating vertices and edges
 begins with a vertex, ends with a vertex, and each edge is
preceded and followed by its endpoints V
a b
 Simple path: A route around a graph that visits every vertex once. P1
d
U X Z
 Euler path: A route around a graph that visits every edge once P2 h
c e
 Examples W g
 P1=(V,b,X,h,Z) is a simple path f
Y
 P2=(U,c,W,e,X,g,Y,f,W,d,V) is a path that is not simple
 Vertices u and v are called connected if there is a path from u
to v

10
 Cont...

 An undirected graph is said to be connected if there exists a path from any vertex to
any other vertex. Otherwise, it is said to be disconnected.

 A graph G is said to be complete (or fully connected or strongly connected) if there

is a path from every vertex to every other vertex.

 Let a and b be two vertices in the directed graph, then it is a complete graph if
there is a path from a to b as well as a path from b to a.
11

 Terminologies (cont.)

 Cycle: circular sequence of alternating vertices and

edges starting and ending point of that path will be the
V
same a b

U d X Z
 Simple cycle: cycle such that all its vertices and edges C2 h
e C1
c
are distinct W g

f
 Examples Y

 C1=(V,b,X,g,Y,f,W,c,U,a) is a simple cycle

 C2=(U,c,W,e,X,g,Y,f,W,d,V,a) is a cycle that is not

simple
12
 Terminologies (cont.)

 Outdegree
 let ‘V‘ be vertex then the starting point of an edge from v to another vertex is known as
out degree.
 Indegree
 let ‘V‘ be vertex and an edge reaches vertex v from another vertex is known as indegree.
 Degree of directed
 let ‘V‘ be the vertex then the degree can be defined as the sum of the total indegree and
total outdegree of the vertex V.
 Sink node of a digraph
 A node of a digraph may be defined as a sink node if outdegree(n)=0 and indegree(n)>0.
 Source node of a digraph
 A node of a digraph may be defined as a source node if outdegree(n)>0 and indegree(n)=0.
13
 Edge Types

 Directed edge: ordered pair of vertices (u,v) first vertex u is the origin second vertex v is
the destination edge (u , v) is not equal to edge (v, u)
 e.g., a flight
 Undirected edge: unordered pair of vertices (u,v), edge (u , v) is equal to edge (v, u)
 e.g., a flight route flight
AA Jimma
AA 1206
 Directed graph all the edges are directed
 e.g., route network AA
X
Jimma
miles
 Undirected graph all the edges are undirected
 e.g., flight network

14
 Graph Representations

 Computer representation of a graph

 Adjacency matrix
 Adjacency lists
Adjacency matrix
 Graph can be represented using a matrix of size total number of vertices by the
total number of vertices.
e.g. a graph with 4 vertices can be represented using a matrix of 4X4 class.
 The adjacency matrix A of a directed graph G = (V, E) can be represented:
Aij = 1 {if there is an edge from Vi to Vj or if the edge (i, j) is a member of E }
Aij = 0 {if there is no edge from Vi to Vj }

15
 Cont...

 Directed graph Undirected graph

16
17
 Efficiency of graph

 In this representation, n2 memory location is required to represent a graph with n vertices.

 The adjacency matrix is a simple way to represent a graph, but it has two disadvantages.

 It takes n2 space to represent a graph with n vertices.

 It takes O(n2 ) time to solve the graph problem.

18
 Adjacency List

 In this representation (also called adjacency list representation), we store a graph as a

linked structure.
 First, we store all the vertices of the graph in a list, and then each adjacent vertices
will be represented using a linked list node.
 Here terminal vertex of an edge is stored in a structure node and linked to a
corresponding initial vertex in the list.

19
 Adjacency List

 Consider the following directed graph representation using linked list

What are the adjacency list and adjacency matrix of the following
graph G1?

20
 Adjacency List vs. Matrix

 Adjacency List
 Use a 1D array of linked lists
 More compact than adjacency matrices if graph has few edges
 Requires more time to find if an edge exists
 Adjacency Matrix
 Use a 2D matrix to represent the graph
 Always require n2 space
 Can quickly find if an edge exists

21
 Graph Representation-

Exercise #1
 Q1. Draw the graphs for the following graph G1 and G2. Write Matrix A to represent graph G3

Adjacency matrixes
0 2
0 1 2 3

0 0 1 1 1
0 1 2 5
1
1 1 0 1 1
00 0 0
2 2 1 0 1
11 0 1 3 4
6
3 1 1 1 0
20 0 0

G1 G2 G3

22
 Traversing a graph

 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 visited in the search
process.

 A graph traversal finds the edges to be used in the search process without creating loops.

 There are two graph traversal techniques

1. DFS (Depth First Search)

2. BFS (Breadth First Search)

23
 DFS (Depth First Search)

 DFS as its name suggest, is to search deeper in the graph, when ever possible.
 DFS traversal of a graph, produces a spanning tree as final result.
 Spanning Tree is a graph without any loops.
 First we visit the starting node. Then we travel through each node along a path, which
begins at S. That is we visit a neighbor vertex of S and again a neighbor of a neighbor
of S, and so on.
 The implementation of DFS is almost same except a stack is used instead of the
queue. Stack data structure with maximum size of total number of vertices is used.

24
 DFS (Depth First Search)

ALGORITHM
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 adjacent vertex of the vertex which is at top of the stack which is
not visited and push it on to the stack.
Step 4: Repeat step 3 until there are no new vertex to be visited from the vertex on top of the
stack.
Step 5: When there is no new vertex to be 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
25
 Example DFS
 The following steps will illustrate the DFS
 Step 1: Initially push I on to the stack.
 STACK: I
 DISPLAY:
 Step 2: Pop and display the top element, and then push all the
neighbors of popped element (i.e., I) onto the stack, if it is not visited
(or displayed or not in the stack.
 STACK: G, H
 DISPLAY: I
 Step 3: Pop and display the top element and then push all the neighbors
of popped the element (i.e., H) onto top of the stack, if it is not visited.
 STACK: G, E
 DISPLAY: I, H
 The popped element H has two neighbors E and G. G is already
visited, means G is either in the stack or displayed. Here G is in the
stack. So only E is pushed onto the top of the stack.
26
 Cont...

 Step 4: Pop and display the top element of the stack. Push all the neighbors of the popped element on to the
stack, if it is not visited.
 STACK: G, D, F
 DISPLAY: I, H, E
 Step 5: Pop and display the top element of the stack. Push all the neighbors of the popped element onto the
stack, if it is not visited.
 STACK: G, D
 DISPLAY: I, H, E, F
 The popped element (or vertex) F has neighbor(s) H, which is already visited. Then H is displayed, and
will not be pushed again on to the stack.
 Step 6: The process is repeated as follows.
 STACK: G
 DISPLAY: I, H, E, F, D
 DISPLAY: I, H, E, F, D, G
27
So I, H, E, F, D, G is the DFS traversal of graph from the source vertex I.

 BFS (Breadth First Search)

 The breadth first search systematically traverse the edges of G to explore every vertex that is
reachable from S.

 Then we examine all the vertices neighbor to source vertex S. Then we traverse all the
neighbors of the neighbors of source vertex S and so on.

 A queue is used to keep track of the progress of traversing the neighbor nodes.

 Queue data structure with maximum size of total number of vertices is used

28
 BFS (Breadth First Search)

ALGORITHM
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 adjacent vertices of the vertex which is at front of the Queue which is not
visited and insert them into the Queue.
Step 4: When there is no new vertex to be visited from the vertex at front of the Queue then
delete that vertex from the Queue.
Step 5: Repeat step 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.

29
 Cont’d

 Step 1: Initially push A (the source vertex) to the queue.

 Step 2: Pop (or remove) the front element A from the queue (by incrementing front = front
+1) and display it.
 Then push (or add) the neighboring vertices of A to the queue, (by incrementing Rear =
Rear +1) if it is not in queue.

30
 Cont’d

 Step 3: Pop the front element B from the queue and display it. Then add the neighboring
vertices of B to the queue, if it is not in queue.

 One of the neighboring element C of B is preset in the queue, So C is not added to queue.
 Step 4: Remove the front element C and display it. Add the neighboring vertices of C, if it is
not present in queue. One of the neighboring elements E of C is present in the queue. So E is
not added.

31
 Cont...

 Step 5: Remove the front element D, and add the neighboring vertex if it is not present in
queue.

 Step 6: again the process is repeated unit front>rear. That is remove front element of E of the
queue and add the neighboring vertex if it is not present in queue.

So A, B, C, D, E, F, G, H is the BFS traversal of the graph

32
 BFS (Breadth First Search)

33
 BFS (Breadth First Search)

34
 BFS (Breadth First Search)

35
 Cont...

The End !!
36