# 算法代写｜COMP2721 Algorithms and Data Structures Coursework 1

1. Execute breadth-first search and depth-first search on the following graph. Start at
vertex a and handle neighbours in alphabetical order. (a) Provide the ordering of the vertices as they are visited by a BFS. Your answer
should be a string σ−1(1)σ−1(2) · ·· σ−1(16) without separators.
[0:15h expected time] [6 marks]

(b) List the neighbours of f in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(c) List the neighbours of g in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(d) List the neighbours of j in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(e) List the neighbours of k in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(f) Provide the ordering of the vertices as they are visited by a DFS.
[0:15h expected time] [6 marks]

(g) List the neighbours of f in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(h) List the neighbours of g in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(i) List the neighbours of j in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(j) List the neighbours of k in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

2. Consider the function Magic, whose pseudocode is illustrated in Algorithm 1. The
algorithm takes a graph as an input and outputs either true or false. The algorithm
also uses a global array p that holds a Boolean value for every v 2 V and a global
integer variable c. ## Algorithm 1: What am I computing?

Given a graph G, then the function Magic returns true if:

• the graph G is connected,
• the graph G has an even number of vertices,
• the graph G has an even number of edges,
• all components of G have exactly two vertices,
• all components of G have an even number of edges,
• all components of G have an even number of vertices.

3. Execute the DFS-based topological sort on the following directed graph. If there is
a choice handle vertices in alphabetic order. (a) Give the first three vertices of the topological ordering as a string
σ−1(1)σ−1(2)σ−1(3) without separators. [0:05h expected time] [2 marks]

(b) Give the next three vertices of the topological ordering as a string
σ−1(4)σ−1(5)σ−1(6) without separators. [0:05h expected time] [2 marks]

(c) Give the next five vertices of the topological ordering.
[0:05h expected time] [2 marks]

(d) Give the next four vertices of the topological ordering.
[0:05h expected time] [2 marks]

(e) Give the final five vertices of the topological ordering.
[0:05h expected time] [2 marks] E-mail: itcsdx@outlook.com  微信:itcsdx 