COMP3023 Design and Analysis of Algorithms
Fall 2021
Programming Assignment
Submission by Nov 28 2021
Instructions:
Write a program that can return any three of the following four artifacts from a given weighted,
undirected graph: (Note each numbered item is considered as one artifact.)
- A Depth-First Search (DFS) Tree (Lecture06)
- All its Articulation Points (AP) and Biconnected Components (BC) (Lecture06)
- A Minimum Spanning Tree (MST), using Kruskal’s Algorithm (Lecture08)
- The Shortest Path Tree (SPT), using Dijkstra’s Algorithm (Lecture09)
The input to your program is a data file named graph.txt, which specifies 1) the number of vertices
(int), 2) the number of edges (int), 3) each edge’s two vertices and its weight (int). A sample input file
is shown in Figure 1, along with the actual graph that it represents:
6
8
0, 1, 3
0, 2, 3
0, 3, 4
1, 3, 3
2, 3, 2
3, 4, 4
3, 5, 2
4, 5, 4
Figure 1 A sample input file with the graph it represents
Your program shall read the file name from keyboard, read the graph information from the file, run
the above-mentioned four algorithms, and display the results on the console. Your program shall
repeatedly ask for an input data file until the user press "CTRL+Z". A sample of console output is given on the
next page, in Figure 2.
Submission: - Please write your program in C or C++.
Put all your code in one single file and name it PA_#######.cpp, where ####### is your
student ID.
Build an executable file and name it PA_#######.exe.
Pack the .cpp and .exe files into a zip file and name it PA_#######.zip. - Please make sure your program can be executed. An unexecutable program will
automatically yield a grade of zero. - 4
- 3 4
- 4 3 4
- 2 2
- 5
2
Input the file name:
graph.txt
- The following are the edges in the constructed DFS Tree
0--1 1--3 2--3 3--4 4--5
- The articulation point(s) found in the given graph is/are:
Vertex 3
The biconnected component(s) found in the given graph is/are:
0--1 0--2 0--3 1--3 2--3
3--4 3--5 4--5
- The following are the edges in the constructed MST:
0--1 1--3 2--3 3--4 3--5
- The following are the edges in the constructed SPT:
0--1 0--2 0--3 3--4 3--5
【COMP3023 Design】Input the file name:
- Comment your code when appropriate. Inside the comments, you are responsible of
providing a full disclosure of all external reference materials that you have used, such as
links to a public webpage, a video tutorial, or even a public repository. Failing to do so may
yield a penalty. - Reusing another student’s program is strictly prohibited. Plagiarism checking will be
conducted prior to grading. Any case of violation of UIC’s honor code will yield a grade of
zero and a report to Student Affairs Office.
Figure 2. Sample console output
推荐阅读
- 程序员|【高级Java架构师系统学习】毕业一年萌新的Java大厂面经,最新整理
- 单片机|自学单片机好找工作吗(会单片机能找什么工作?)
- c语言|一文搞懂栈(stack)、堆(heap)、单片机裸机内存管理malloc
- Python|教你写个简单好用的Python脚本一键自动整理文件非常适合办公用~
- 为了搭建冬奥会志愿者系统,他独自跨越大半个中国学习低代码
- 程序员|程序员“真实”日常(每天敲代码不到 1 小时)
- GitHub|7 款可替代 top 命令的工具
- 程序员|自学编程,学完新的又忘旧的,该怎么办()
- 程序员|Python和C究竟选哪个()
- 程序员|5 分钟解决前后端联调问题,说一说前端代理这件事