Mizan-Tepi University

School of Computing and Informatics

Department of Software Engineering

Chapter Six

Graphs Data Structure

By:- Melkamu D.(M.Sc.)

Dec, 2023

MTU, Ethiopia
 Mizan-Tepi University

Graph
 A graph is a nonlinear data structure.
 A data structure that consists of a set of nodes (vertices) and a set of edges that relate
the nodes to each other.
 The set of edges describes relationships among the vertices.
 Formal definition of graphs
 A graph G is defined as follows:G=(V,E):
 V(G): a finite, nonempty set of vertices.
 E(G): a set of edges (pairs of vertices).
 Each edge is a pair (v,w) where v, w  V.
 Node:
 has a unique label for identification.
 Mizan-Tepi University

Cont.…..
 Edge
 connects two nodes.
 can be a
 directed edge

A B D

 undirected edge

C E F
 Mizan-Tepi University

Terminologies
1. Adjacent vertices: Two vertices are said to be adjacent if they are connected by an edge.
 e.g., B and C are adjacent to vertex A because separate edges connect B and C
to A.
2. Adjacent edges: Two edges are said to be adjacent if they are incident on the common vertex.
 e.g., edges CD and CE are adjacent because they are incident on the common vertex C.
3. Path: connected sequence of edges:
 e.g. A to B to D to C to E
 if the edges are directed then the path has to follow the directions of the edges.
4. A cyclic path is a path such that:
 There are at least two vertices on the path:
w1 = wn (path starts and ends at same vertex)
i.e. a cycle is a path that goes in a loop from a node back to itself, and without using the same
node twice.
 Mizan-Tepi University

Cont.…
E.g. A-B-E-A in
B
A
F
D
C

E G

5. LOOP: It is a special cycle that starts and ends with the same vertex without visiting
any other vertex.
 An acyclic path is a path where each vertex is unique.
 An “acyclic graph” has no cycles.
 Mizan-Tepi University

Cont.…
6. Degree of a vertex: The degree of a vertex is the number of lines incident on it.
7. In-degree: The in-degree of a directed graph is the number of arcs entering the vertex.
8. Out-degree: The out-degree of a directed graph is the number of arcs leaving the
vertex.
9. Connected vertices: Two vertices are said to be connected if there is a path between
them.
 Test Your Knowledge
Q1: Is it a Cyclic or Acyclic graph ???
 Mizan-Tepi University

Cont.…
Q2: What are the in-degrees and out-degrees of the vertices a, b, c, d in this graph???

deg-(a) = 1 a deg-(b) = 4
deg+(a) = 2 b deg+(b) = 2

deg-(c) = 0
deg (d) = 2
-
d c deg+(c) = 2
deg+(d) = 1
 Mizan-Tepi University

Types of Graph
1. Simple graph: A graph that does not contain any loop or multiple edges between
two vertices is called a simple graph.
A B D

C E F

2. Multi-graph: A graph that contains more than one edge between two vertices is called
a multi-graph.
B D
Example:

C E F
 Mizan-Tepi University

Cont.….
3. A directed graph also known as a digraph is a graph in which its edges(links) have
direction, i.e. the edges are arrows. Directed graphs show the flow from one node to
another but not vice versa. For example, a directed graph ‘G’ where,
=>G = ( {a, b, c, d }, {( a, b), (a, d), (d, b), (d, d), (c, c)} )

4. Undirected graph also known as a uni-graph is a graph in which its edges do not have
a direction.
 Mizan-Tepi University

Cont.…
5. Weighted graph: A graph is known as a weighted graph if a weight or metric is
associated with each edge.

6. Complete graph: An undirected graph that has an edge between every pair of vertices
is called a complete graph.
Note: A directed graph can also be a complete graph; in that case, there must be an edge
from every vertex to every other vertex.
 Mizan-Tepi University

Representation of Graph
 Graphs can be represented by their adjacency matrix or an edge (or vertex) list. i.e.
1. Sequential representation using adjacency matrices.
2. Linked representation using an adjacent list or linked list of neighbors.(reading assignment)
Adjacency matrices have a value ai, j = 1 if nodes i and j share an edge; 0 otherwise.
 Representing Graphs
Vertex Adjacent Vertices
a

b a b, c, d

d b a, d

c c a, d

d a, b, c
 Mizan-Tepi University

Sequential Representation using Adjacency Matrix

 Mizan-Tepi University

Traversal of Graphs
 Some applications of the graph require systematically visiting all the nodes.
 In a graph, we can reach the vertex from multiple paths existing in the graph, so we can say that graph
traversal is not as simple as traversal in other data structures.
 There are two standard traversal methods generally used with graphs:
1. Breadth-first search(BFS)
2. Depth-first search(DFS)
 Breadth-first search(BFS)
 BFS is that it starts traversing the graph from the starting node (any selected node) and then traverses all the
nodes that are directly connected to the starting node in a particular order.
 First, the starting node is examined and all the adjacent nodes are placed into the queue.
 The node traversed is marked as visited.
 The next node is taken from the front of the queue and examined;
 This node is also marked as visited and all the neighbors of this node are placed into the rear of the queue.
 In BFS all the nodes at a particular level are processed first, only then can we move to the next level.
 Mizan-Tepi University

BFS algorithm
1. Start traversing the given graph with the given number of vertices and edges.
2. Insert the starting source vertex S into the queue and mark it as visited.
3. Repeat
a. Remove the front node K of the queue and examine it.
b. Insert all the adjacent nodes of K (which have not visited so far) into the queue and
mark them as visited
4. Until the queue is empty
5. Exit A C

Note: The Implementation of BFS takes place by using in queues. F

Example: Traverse the following graph using the BFS starting from E. B D

E
 Mizan-Tepi University

Solution
Step 1: start traversing the graph given.
Step 2: Insert the starting source vertex E to the queue and mark it as visited.
E F=0,R=0

0 1 2 3 4 5
Step 3: Take the front node E. Examine it.
Step 4: insert all the adjacent nodes of E to queue named as Q and mark them as visited.
B F F=0,R=1

0 1 2 3 4 5
Mizan-Tepi University

Solution
Mizan-Tepi University

Solution
Mizan-Tepi University

Solution
 Mizan-Tepi University

Depth First search

 The traversal starts at the starting source vertex and traverses all the nodes along
the path which begins at the source vertex.
 The implementation of the DFS is similar to the BFS except that stack is used
in place of queue.
DFS algorithm
1.Start traversing the given graph with the given number of vertices and edges.
2. Push the starting source vertex S to the stack and mark it as visited.
3. Repeat
a. Remove the top node K of the stack and examine it.
b. Push all adjacent nodes of K(which are not visited so far)to the stack and mark them as
visited
4. Until stack is empty
5. Exit
 Mizan-Tepi University

Cont.…
 Example: Traverse the following graph using the DFS starting from A.

A C

B D

E
 Mizan-Tepi University

Solution
Step 5: take away(pop) the top node B. examine it.
Step 6: Insert all the adjacent node of B to the stack in any order and mark them as
visited.

Step 7: take away(pop) the top node D. examine it.

Step 8: Insert all the adjacent node of D to the stack.
B and C are already marked as visited
 Mizan-Tepi University

Solution
Step 9: take away(pop) the top node F. examine it.
Step 10: Insert all the adjacent node of F to the stack. D, C and E are already marked as
visited.

Step 11: take away(pop) the top node E. examine it.

Step 12: Insert all the adjacent node of F to the stack.
B and F are already marked as visited.
 Mizan-Tepi University

Cont.…
Step 13: take away(pop) the top node C. examine it.
Step 14: Insert all the adjacent node of F to the stack. A,B ,D and F are already marked as
visited.

Step 15: Stop now because stack is empty.

 Therefore, The DFS order is ABDFEC
 Mizan-Tepi University

Summary questions
Q: What is the BFS & DFS of the figure depicted here starting from 10 and 0 respectively???
 :
Mizan-Tepi University

End of Chapter Six

Yo u!!
a nk
Th
n s ?
Qu est io