CS223: Data Structures, Fall 2020/2021 Programming Assignment 4 Due Date: Jan 15, 11:59 PM a) Write a C++ program that provides an implementation for an undirected weighted graph. You can use either the adjacency matrix or adjacency list to represent the graph. When the user enters the number of vertices (say 5), there will be five vertices (each generated vertex will be assigned with a value sequentially from 1 to 5). The input for edges should consist of three 3 values (e.g., 14 20), 1 and 4 are the vertices of the edge and 20 is the edge's weight. b) The program should support breadth-first traversal using a Queue using a linked list data structure (needs to specify the source vertex from user). c) The program should support depth-first search using a stack using a linked list data structure (needs to specify the source vertex and value to be searched from user). d) The program should support finding the minimal spanning tree using Kruskal's algorithm prints the edges that are part of a minimal spanning tree of the corresponding graph, and prints the minimal spanning tree's total weight. e) The program should support finding the minimal spanning tree using prim's algorithm, prints the edges that are part of a minimal spanning tree of the corresponding graph, and prints the minimal spanning tree's total weight (needs to specify the source vertex from user). The program should show a menu that enables the user to choose from multiple operations (as listed above). Based on the choices of the user, the program should be able to handle any case. An example of a menu is as follows (the menu should be customized to include all required functionalities): **Menu 1. Insert the number of vertices 2. Insert Edge 3. Breadth First Traversal 4. Depth First Search 5. Find MST using Kruskal's algorithm and print the edges and total weight of the tree. 6. Find MST using Prim's algorithm and print the edges and total weight of the tree. 7. Exit Enter your choice (value between 1-7): CS223: Data Structures, Fall 2020/2021 Programming Assignment 4 Due Date: Jan 15, 11:59 PM a) Write a C++ program that provides an implementation for an undirected weighted graph. You can use either the adjacency matrix or adjacency list to represent the graph. When the user enters the number of vertices (say 5), there will be five vertices (each generated vertex will be assigned with a value sequentially from 1 to 5). The input for edges should consist of three 3 values (e.g., 14 20), 1 and 4 are the vertices of the edge and 20 is the edge's weight. b) The program should support breadth-first traversal using a Queue using a linked list data structure (needs to specify the source vertex from user). c) The program should support depth-first search using a stack using a linked list data structure (needs to specify the source vertex and value to be searched from user). d) The program should support finding the minimal spanning tree using Kruskal's algorithm prints the edges that are part of a minimal spanning tree of the corresponding graph, and prints the minimal spanning tree's total weight. e) The program should support finding the minimal spanning tree using prim's algorithm, prints the edges that are part of a minimal spanning tree of the corresponding graph, and prints the minimal spanning tree's total weight (needs to specify the source vertex from user). The program should show a menu that enables the user to choose from multiple operations (as listed above). Based on the choices of the user, the program should be able to handle any case. An example of a menu is as follows (the menu should be customized to include all required functionalities): **Menu 1. Insert the number of vertices 2. Insert Edge 3. Breadth First Traversal 4. Depth First Search 5. Find MST using Kruskal's algorithm and print the edges and total weight of the tree. 6. Find MST using Prim's algorithm and print the edges and total weight of the tree. 7. Exit Enter your choice (value between 1-7)
