代写220SC程序、代写Python程序设计

日期：2023-05-16 08:52

Computer Science 220SC (2023)

Assignment 3 (Basic graph algorithms and traversals)

See Canvas for due date

This assignment requires you to submit programs in Python that you have written yourself

to the automarker, https://www.automarker.cs.auckland.ac.nz. Your implementation

must be from first principles and cannot use an existing library methods that might solve

the problem (eg performs graph operations etc).

The automarker runs on a Linux box. Read the automarker help and FAQ for more

details.

Please submit only Python source code (.py or .py3 extensions only).

1. Delete a node from a digraph and record number of arcs removed 30 Marks

For each digraphs in a set of digraphs given as adjacency lists, read in the digraph,

delete the node with index n − 3 where n is the order of the digraph, and write the

digraph back to the terminal. After the adjacency lists, write out how many arcs

have been removed in the process. Assume input digraphs have order at least 3.

Input format: described below under the heading “Digraph input format”.

Output format: the same as the input format but with one extra line after each

digraph stating the number of arcs that were removed when the node was removed.

Ensure that you maintain the node naming conventions.

For the example input shown below, the first digraph would have node with index

1 removed, and the second graph would have node index 0 removed, so the output

would be

Here the first line indicates the order of the new digraph is 3, the next three lines

are the three adjacency lists showing the arcs of the this digraph, and the 3 on line

5 indicates that three arcs were removed from the input digraph. The next line has

a 2 indicating that the next digraph has order 2 and so on.

1

2. Back and cross arcs in a DFS 30 Marks

For a given set of digraphs, write a program that performs DFS on each digraph

starting at node 0 and prints out the total number of back arcs and cross arcs resulting

from the traversal. Use our standard convention that when there is a choice of white

or grey nodes, the one with the lowest index should be chosen.

Input format: described below under the heading, “Digraph input format”.

Output format: For each input digraph, print out a line with the number of back

arcs, then whitespace, and then the number of cross arcs.

For the example input shown below, the output would be

1 0

0 1

3. BFS to find distances 30 Marks

Write a program that performs BFS on each of a given set of digraphs starting at

node 1 and prints the distance to the most distant node from 1 and reports the node

with the highest index at that distance. Nodes that are not reachable from 1 have

an undefined distance and should be ignored.

Input format: described below under the heading, “Digraph input format”.

Output format: For each input digraph, print out a line with the distance to the

most distant node, then a space, then the highest index of a node at that distance.

Ignore nodes that are not reachable from 1.

For the example input shown below, the output would be

2 0

0 1

2

Digraph input format

A sequence of one or more digraphs is taken from the standard input (eg sys.stdin). Each

graph is represented by an adjacency list. The first line is an integer n indicating the order

of the graph. This is followed by n white space separated lists of adjacencies for nodes

labeled 0 to n - 1. The lists are sorted. The input will be terminated by a line consisting

of one zero (0). This line should not be processed. The sample input below shows two

digraphs, the first has node set {0, 1, 2, 3} and arc set {(0, 1),(0, 3),(1, 2),(1, 3),(2, 0)}, the

second has node set {0, 1, 2} and arc set {(0, 1),(0, 2),(2, 1)}.

Marking

The maximum number of submissions for each problem is fixed at 12.

Each problem has 3 test cases associated with it worth one third of the marks for that

problem. Some of the test cases will be large. You get full marks if you pass all test

cases.

3