CS 2123 Data Structures Programming Project 6 In this project, we will be computing a shortest path between two vertices of an unweighted graph using Breadth First Seh (BFS). BFS uses a Queue, and we will implement the Queue as well Files provided in the project: Queue.h. This file contains the prototypes and definitions for the functions for a queue. The i and Queues" document on Blackboard. You need to implement the following functions in the file Queue.c 1) tion of most of these functions was in the "Linked List a. Queue newQueue). Malloc a new queue, initialize its values, and return its address. b. void freeQueue(Queue q). Free all the remaining nodes in the Queue and then free c. NodeQ 'allocateNodeQ(Vertex v). Given a vertex of the graph, malloc a node to d. void insertQ(Queue q, Vertex v). Add a new node containing v and add it to the end e. int removeQ(Queue q, Vertex v). Attempts to remove the node at the head of the the Queue itself store this node and return its address. of the queue. queue. If the queue is empty, it returns FALSE. If the queue is not empty, it returns the vertex through (passed by reference) and functionally returns TRUE 2) Graph.h. This file contains the prototypes of all of the functions we will be using for an adjacency matrix implementation of a Graph. You must provide the implementation of the following functions in Graph.c Graph newGraph(int n). This function takes as input the number of vertices of the graph, and mallocs a new graph, mallocs an nxn array for the adjacency matrix of the graph, initializes each value of the matrix to be 0 (no edges yet), and then returns the address of the graph. a. b. void freeGraph(Graph g). Free the adjacency matrix and then the graph itself c. void addEdge(Graph g, Edge e). Given a graph and an edge, set the corresponding entry in the adjacency matrix to be 1 Edge firstAdjacent(Graph g, Vertex v). Given a graph and a vertex v, return the first edge of the graph that has v as the "fromVertex". If no such edge exists return an edge with both the fromVertex and toVertex set to be-1. Edge nextAdjacent(Graph g, Edge e). Given a graph g and an edge e, find the next edge in g after e that has the same "fromVertex" as e. If no such edge exists return an edge with both the fromVertex and toVertex set to be -1. d. e. CS 2123 Data Structures Programming Project 6 In this project, we will be computing a shortest path between two vertices of an unweighted graph using Breadth First Seh (BFS). BFS uses a Queue, and we will implement the Queue as well Files provided in the project: Queue.h. This file contains the prototypes and definitions for the functions for a queue. The i and Queues" document on Blackboard. You need to implement the following functions in the file Queue.c 1) tion of most of these functions was in the "Linked List a. Queue newQueue). Malloc a new queue, initialize its values, and return its address. b. void freeQueue(Queue q). Free all the remaining nodes in the Queue and then free c. NodeQ 'allocateNodeQ(Vertex v). Given a vertex of the graph, malloc a node to d. void insertQ(Queue q, Vertex v). Add a new node containing v and add it to the end e. int removeQ(Queue q, Vertex v). Attempts to remove the node at the head of the the Queue itself store this node and return its address. of the queue. queue. If the queue is empty, it returns FALSE. If the queue is not empty, it returns the vertex through (passed by reference) and functionally returns TRUE 2) Graph.h. This file contains the prototypes of all of the functions we will be using for an adjacency matrix implementation of a Graph. You must provide the implementation of the following functions in Graph.c Graph newGraph(int n). This function takes as input the number of vertices of the graph, and mallocs a new graph, mallocs an nxn array for the adjacency matrix of the graph, initializes each value of the matrix to be 0 (no edges yet), and then returns the address of the graph. a. b. void freeGraph(Graph g). Free the adjacency matrix and then the graph itself c. void addEdge(Graph g, Edge e). Given a graph and an edge, set the corresponding entry in the adjacency matrix to be 1 Edge firstAdjacent(Graph g, Vertex v). Given a graph and a vertex v, return the first edge of the graph that has v as the "fromVertex". If no such edge exists return an edge with both the fromVertex and toVertex set to be-1. Edge nextAdjacent(Graph g, Edge e). Given a graph g and an edge e, find the next edge in g after e that has the same "fromVertex" as e. If no such edge exists return an edge with both the fromVertex and toVertex set to be -1. d. e