辅导220SC程序、辅导Python程序设计

日期：2023-05-17 08:11

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