本次新西兰代写主要为图算法相关的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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。