CS 3050 Final Lab: Spanning Trees and Graph Algorithms

Instructions

Each problem is implemented in C. Compile using gcc or a similar compiler.

You must complete the logic in each main.c file and comment your code.

Submission:

1. Fork the repository
2. Clone locally
3. Complete each of the five problems.
4. For each problem, in addition to the code, submit:
   • Your personal explanation of each choice you made in preparing your code: in a file explain.md, contained in that problem's directory.
   • A short description (2-3 paragraphs) describing the utlity of the algorithm in that particular question: in a file explain.md in that problem's directory.

Problems

• problem1_update_mst/main.c: Update MST when a new vertex and incident edges are added
• problem2_prim_kruskal_order/main.c: Compare edge orders of Prim's and Kruskal's algorithms
• problem3_edge_in_mst/main.c: Check if a given edge is in the MST
• problem5_aug_data_struct/main.c: Compute MST of an almost-tree (|V| = |E|)*
• problem5_red_black/main.c: Compute Bottleneck Spanning Tree*

**Solutions should be zipped up and submitted via canvas by 11:50pm on Saturay, May 17th.