HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN TOÁN RỜI RẠC 2
BÁO CÁO BÀI TẬP LỚN
Giảng viên hướng dẫn :Nguyễn Thị Mai Trang
Họ và tên sinh viên :Hoàng Văn Huynh-B23DCDT131
Lớp : D23CQCE02 - B
Hà Nội – 2025
1
Contents
Exercise 1: Use the DFS algorithm to traverse an undirected or directed graph in two
cases:..............................................................................................................................3
*Algorithm:................................................................................................................3
*Program code:...........................................................................................................5
Exercise 2: Use DFS and BFS algorithms to count the number of connected
components in an undirected graph...............................................................................6
*Algorithm:................................................................................................................6
*Program code:............................................................................................................7
Exercise 3: Checking Strong Connectivity of a Directed Graph................................10
*Algorithm:..............................................................................................................10
*Program Code:........................................................................................................10
Exercise 4: Check if the Graph is Eulerian and Find an Eulerian Cycle(Directed or
Undirected)..................................................................................................................15
*Algorithm:..............................................................................................................15
*Program code:.........................................................................................................16
2
Exercise 1: Use the DFS algorithm to traverse an undirected or
directed graph in two cases:
Input 1: Enter the adjacency matrix.
Input 2: Enter the incidence matrix.
Output: Print the order of vertices visited by the DFS
(Depth-First Search) algorithm.
*Algorithm:
DFS Algorithm: Begin
Step 1 (Initialize):
stack = ∅; //Initialize an empty stack
Push(stack, u); //Push vertex u onto the stack
<visit vertex u>; //Traverse u
visited[u] = true: //Mark vertex u as traversed
Step 2 (Loop):
while (stack ≠ ∅) do
s = Pop(stack); //Remove the top element
from the stack
for each t ∈ Ke(s) do //For each
vertex
adjacent to s if(!
visited[t]) then // if vertex t is untraversed
<visit vertex t>; // Traverse t
visited[t] = true; // Vertex t is traversed
Push(stack, s); // Push s back onto stack
3
Push(stack, t); // Push t onto the stack
break; //Only take one neighbor t
EndIf;
EndFor;
EndWhile;
Step 3 (Return result):
Return(<Set of visited vertices>);
End.
4
*Program code:
5
Exercise 2: Use DFS and BFS algorithms to count the number of
connected components in an undirected graph.
Input:
o Enter the algorithm selection:
• If key ‘1’ is entered, use the DFS (Depth-First
Search) algorithm.
• If key ‘2’ is entered, use the BFS (Breadth-First
Search) algorithm.
o Enter the adjacency matrix of the undirected graph.
Output:
Display each connected component and the total number of
connected components in the graph.
*Algorithm:
ConComp(){
Step 1 (Initialize)
count = 0; //Number of connected components equals to 0
Step 2 (Loop)
for(u ∈ V){ //For each vertex
if(unTraverse[u]){
count = count + 1;//A connected component
BFS(u); //or DFS(u)
<store vertices of the connected component>;
}
}
Step 3(Return result)
6
Return <connected components>;
}
*Program code:
7
8
Exercise 3: Checking Strong Connectivity of a Directed Graph.
Input:
o Enter the algorithm selection:
• If key ‘1’ is entered, use the DFS (Depth-First
Search) algorithm.
• If key ‘2’ is entered, use the BFS (Breadth-First
Search) algorithm.
o Enter the adjacency matrix of the directed graph.
Output:
Print the traversal from each vertex of the graph and check
whether the graph is strongly connected or not.
*Algorithm:
Boolean Strong-Connective ( G = <V,E> ) {
ReInit(); // For all u ∈ V: visited[u] = True;
for each u ∈ V do { // Take each vertex in V
if (DFS(u) ≠ V) then // If DFS(u) V or BFS(u) V
return(False); // The graph is not strongly
connected
endif;
ReInit(); // Reinitialize the visited[] array
}
return(True); // The graph is strongly connected
}
*Program Code:
9
10
11
Input 2:
Output 2:
12
Exercise 4: Check if the Graph is Eulerian and Find an Eulerian
Cycle (Directed or Undirected).
Input:
o Enter the type of graph to check:
• If key ‘1’ is entered: Directed graph
• If key ‘0’ is entered: Undirected graph
o Enter the adjacency matrix of the graph.
Output:
If the graph is not Eulerian, print "No".
Otherwise, print "Yes" and display the Eulerian Cycle of
the graph.
*Algorithm:
Euler-Cycle Algorithm (u) :
stack = ∅; // Initialize an empty stack
Step 1 (Initialization):
CE = ∅; // Initialize an empty array CE
Push(stack, u); // Push vertex u onto the stack
while (stack ≠ ∅) do { // Loop until stack is empty
Step 2 (Loop):
if (Ke(s) ≠ ∅) then { // If the adjacency list Ke(s) is not
s = get(stack); // Get the top vertex from the stack
empty
t = <first vertex in Ke(s)>; // Take the first vertex in
Ke(s)
Push(stack, t); // Push t onto the stack
E = E \ (s,t); // Remove edge (s,t) from the graph
}
else { // When Ke(s) is empty
s ⇒ CE; // Append s to CE
s = Pop(stack); // Pop s from the stack
}
}
Step 3 (Return Result):
13
Reverse the vertices in CE to get the Eulerian cycle
*Program code:
14
15
16
Input 2:
Output 2:
17
