03/05/2021 COMP2521 - Graphs Practice Exercises
https://www.cse.unsw.edu.au/~cs2521/20T1/practice/graphs/numReachable/ 1/2
numReachable
Your task is to write a function, numReachable, that returns the number of vertices that are reachable from a source vertex in the given
graph, including the source vertex itself.
Download
Click here to download a zip of the files.
The Files
Graph.c Contains the implementation of a graph ADT
Graph.h Contains the interface of the graph ADT
testNumReachable.c Contains the main function, which reads in a graph from standard input, calls numReachable for each vertex
read in, and prints out the results.
numReachable.c Contains numReachable, the function you must implement
Makefile A makefile to compile your code
tests/ A directory containing the inputs and expected outputs for some basic tests
autotest A script that uses the tests in the tests directory to autotest your solution. You should only run this after you
have tested your solution manually.
Examples
Your program should behave like these examples:
$ ./testNumReachable
Enter number of vertices: 12
Enter number of edges: 11
Enter edges in the form v-w: 0-8 0-3 3-8 0-10 10-2 1-9 1-5 5-9 4-6 4-7 4-11
Graph: nV = 12
Edges:
0: 0-3 0-8 0-10
1: 1-5 1-9
2: 2-10
3: 3-0 3-8
4: 4-6 4-7 4-11
5: 5-1 5-9
6: 6-4
7: 7-4
8: 8-0 8-3
9: 9-1 9-5
10: 10-0 10-2
11: 11-4
Enter the source vertex: 2
Number of vertices reachable from vertex 2: 5
Enter the source vertex: 1
Number of vertices reachable from vertex 1: 3
Enter the source vertex: 4
Number of vertices reachable from vertex 4: 4
Enter the source vertex: (Ctrl + D)

03/05/2021 COMP2521 - Graphs Practice Exercises
https://www.cse.unsw.edu.au/~cs2521/20T1/practice/graphs/numReachable/ 2/2
$ ./testNumReachable
Enter number of vertices: 12
Enter number of edges: 7
Enter edges in the form v-w: 0-1 2-3 3-4 5-9 5-10 9-11 10-11
Graph: nV = 12
Edges:
0: 0-1
1: 1-0
2: 2-3
3: 3-2 3-4
4: 4-3
5: 5-9 5-10
6:
7:
8:
9: 9-5 9-11
10: 10-5 10-11
11: 11-9 11-10
Enter the source vertex: 3
Number of vertices reachable from vertex 3: 3
Enter the source vertex: 6
Number of vertices reachable from vertex 6: 1
Enter the source vertex: 5
Number of vertices reachable from vertex 5: 4
Enter the source vertex: (Ctrl + D)

Testing
You can test your program manually by compiling your code using make, and then running ./testNumReachable, as shown above. After
you are satisfied with your solution, you can autotest it by running ./autotest. This will run some basic tests on your program.

欢迎咨询51作业君