2023年11月25日

图算法代写 | COMPSCI 220 S1 Assignment 3

本次新西兰代写主要为图算法相关的assignment

COMPSCI 220 S1 COMPSCI 220 S1 Assignment 3

There are 3 problems listed below. To get full marks for this assignment you need to complete all of them!
The marks for this assignment are worth 7.5% of your course grade. The due date is rm in that there are
no penalty options available for late submissions (except zero marks).
Please submit a single PDF le with your solutions to Questions 1-2 to Canvas. A (scanned) handwritten
report is ne as long as it is neat. Show all working; if you do not show your work marks will be reduced.
Your answer to Question 3 must be submitted via the automated marker system at
https://www.automarker.cs.auckland.ac.nz
Academic integrity notice. Sharing assignment solutions or source code does not help learning. Con-
sequently, our academic integrity policy does not permit the sharing of solutions or source code leading to
solutions. Violation of this will result in your assignment submission attracting no marks and you may face
disciplinary actions. Please do not share (online or otherwise) assignments, assignment solutions and/or
source code leading to assignment solutions. You can refer to online tutorials and resources. However,
please learn from them and write up solutions yourself based on what you have learned from those sources.
1. DFS and BFS.
(a) Apply DFS to the following graph and give the order of the vertices in which they get visited. If
there are several choices, choose the vertex with the smallest number.
(5 mark)

(b) Apply BFS to the following graph and give the order of the vertices in which they get visited. If
there are several choices, choose the vertex with the smallest number.
(5 mark)
(c) Draw a directed graph of your choice with 10 nodes and 12 arcs. Each node is labeled with an
element in f0; 1; 2; : : : ; 9g so that no two nodes have the same label. Apply DFS to this graph,
give the order of the vertices in which they get visited. If there are several choices, choose the
vertex with the smallest number. Classify each arc as a tree arc, cross arc, back arc or forward
arc.
(5 mark)
2. Reverse digraph.
Let G = (V;E) be a digraph. You are given G as an adjacency matrix. In your own words, describe
an ecient algorithm for computing the adjacency matrix representations of the reverse digraph of G.
Give the running time of your algorithm.

3. Graph algorithms.
The square of a directed graph G = (V;E) is the graph G2 = (V;E2) such that (u; v) 2 E2 if and only
if G contains a (directed) path with exactly two arcs from u to v.
Write two algorithms to solve the following two algorithmic tasks for digraphs.
(a) For a list of digraphs, print out the same digraphs as adjacency matrices.
(15 marks, 6 marks for the rst and 9 marks for the second test case)
(b) For a list of digraphs, print out the square of each digraph.
(15 marks, 5 marks for each of the three test cases)
Please provide a separate program to solve each task.
Input format for (a) and (b). The input consists of a sequence of one or more digraphs. Each
digraph D is represented by an adjacency list. The rst line is an integer n that indicates the order
of D. This is followed by n white space separated lists of adjacencies for nodes labeled 0 to n 1.