22127449 – Mai Đức Vân
22127450 – Phạm Anh Văn
Problem 1:
Graph (a): Directed graph
The orders of each vertex:
Vextex In-Degree Out-Degree
0 1 1
1 2 2
2 1 1
3 1 1
4 1 1
Graph (b): Undirected graph
All vertices except center vertices have degree 3
Center vertex has degree 4.
Problem 2:
In fig 1, begins with vertex 0. I have list the vertical in order: \
DPS strategy:
Stack 0 1 2 3 4
Vertex 0 1 2 4 3
BFS strategy:
Stack 0 1 2 3 4
In Order 0 1 2 3 4
Problem 3:
Adjacency Matrix:
0 1 2 3 4
0 0 1 0 0 0
1 0 0 1 1 0
2 0 0 0 0 1
3 0 1 0 0 0
4 1 0 0 0 0
Problem 4:
All way we will have:
a,g,d,b,e,c,f
g,a,d,b,e,c,f
a,g,d,b,e,f,c
g,a,d,b,e,f,c
Problem 5:
Adjacency List:
Node Adjacency List
0 4,1
1 0,2,4
2 1,5,3
3 2
4 0,1,5
5 2,4
Adjacency matrix:
0 1 2 3 4 5
0 ∞ 9 ∞ ∞ 1 ∞
1 9 ∞ 8 ∞ 6 ∞
2 ∞ 8 ∞ 5 ∞ 2
3 ∞ ∞ 5 ∞ ∞ ∞
4 1 6 ∞ ∞ ∞ 7
5 ∞ ∞ 2 ∞ 7 ∞
Problem 6:
No, because if we want to make a graph contain a simple cycle, it must have at
least one more edge than the number of vertices. In the other hand, we only have 4
edge and 5 vertices, which means the graph is likely a tree, a line or a disconnected
graph.
Problem 7:
Adjacency list:
Node Adjacency list
a b,c
b d,h
c d,e
d h
e g
f g,i
g c
h g
i None
Adjacency matrix:
a b c d e f g h i
a 0 1 1 0 0 0 0 0 0
b 0 0 0 1 0 0 0 1 0
c 0 0 0 1 1 0 0 0 0
d 0 0 0 0 0 0 0 1 0
e 0 0 0 0 0 0 1 0 0
f 0 0 0 0 0 0 1 0 1
g 0 0 1 0 0 0 0 0 0
h 0 0 0 0 0 0 1 0 0
i 0 0 0 0 0 0 0 0 0
Problem 8:
Here is pseudocode to check cycle in graph by DFS:
function hasCycle(graph):
visited = array of size V (number of vertices), initialized to False
recursion = array of size V, initialized to False
for each vertex v in graph:
if not visited[v]:
if hasCycleByDFS(graph, v, visited, recursion):
return True
return False
----------------------------------------------------------------------------
function hasCycleByDFS(graph, v, visited, recursion):
visited[v] = True
recursion[v] = True
for each adjacent vertex u of v:
if not visited[u]:
if hasCycleByDFS(graph, u, visited, recursion):
return True
else if recursion[u]:
return True
recursion[v] = False
return False
