All submissions must be done on e-learning only. class Graph int V; W No. of vertices list int> *ady; public: Graph(int V) this->V = V; adj - new list int>[V]; } -Graph() delete l adj; void addEdge (int v, int w) { adj[v].push_back (w): } ); Answer the following questions using the above class. You are allowed to add public or private member functions as needed. (20 points) Back Edges Implement the member function void Graph::printAllBackEdges (). This function prints all back edges in the current graph. (20 points) Undirected Graph Implement the member function bool Graph::isundirectedGraph(). This function checks if the graph can be treated as an undirected graph. (Hint: if for every edge (u, v) in the graph the edge (v, u) also exists, then the graph can be treated as an undirected graph). (20 points) Given a directed graph, describe an efficient algorithm for checking if there is a vertex v in the graph from which all other vertices are reachable. What is the order of growth of the running time of your algorithm in the worst case? (Note: inefficient algorithms will receive partial credit). (15 points) Connected Components (1) Consider the following modified version of class Graph for representing undirected graphs: class Graph int V: No. of vertices list int> *ady: // Each vertex belongs to a connected component in the graph. /1d[0] stores the id of the connected component vertex o belongs to, Wid[1] stores the component id for vertex 2, etc. Widtuj - idivl if and only if u and v belong to the same component int. id; public: Graph (int i) { this->V - V; adj - new listint>[V]; 1 -Graph() { delete I) ad)) void addEdge (int v, int w) adh tv).push_back(): adj[w]).push_back(v); 1 bool sameComponent(int , int w) { return id[v] - id (w): 1 ); A. Perform the following modifications so that function sameComponentiv, w) correctly returns true if vertices v and w are in the same component: a. Modify the constructor so that the array id is allocated with size V. Initialize the array such that each vertex in the graph is in a separate component. b. Modify function addEdge so that the components are updated (if necessary) each time a new edge is added. Example 0 0 1 0 2 2 3 3 4 3 0 0 1 0 WN 3 3 4 3 0 0 1 0 WN | 4 3 B. What is the order of growth of the running time of creating a complete graph using the addEdge function you have created? (25 points) Connected Components (2) Consider the following modified version of class Graph for representing undirected graphs: class Graph int V; // No. of vertices list int> *ady; // Each vertex belongs to a connected component in the graph. // id[0] stores the id of the connected component vertex 0 belongs to, Wid[11 stores the component id for vertex 1, etc. // id[u] -- id[v] if and only if u and v belong to the same component int* id; public: Graph (int V) this->V = V; adj = new list
[V]: -Graph() / delete [1 adj; } void addEdge (int v, int w) adj [v].push_back(w); adj[w] .push_back (v); 2 bool connectedComponents() { } Implement function connectedComponents() such that it finds all the connected components in the graph, fills the array id and returns it. Note the following: You are not allowed to modify the constructor or function addEdge. All the computation must be done inside function connectedComponents or inside other functions called from within connectedcomponents. You are allowed to add private data members and private or public member functions as needed. . Function connectedcomponents must run in time that is at most linear in the graph size (i.e. O(E+V). All submissions must be done on e-learning only. class Graph int V; W No. of vertices list int> *ady; public: Graph(int V) this->V = V; adj - new list int>[V]; } -Graph() delete l adj; void addEdge (int v, int w) { adj[v].push_back (w): } ); Answer the following questions using the above class. You are allowed to add public or private member functions as needed. (20 points) Back Edges Implement the member function void Graph::printAllBackEdges (). This function prints all back edges in the current graph. (20 points) Undirected Graph Implement the member function bool Graph::isundirectedGraph(). This function checks if the graph can be treated as an undirected graph. (Hint: if for every edge (u, v) in the graph the edge (v, u) also exists, then the graph can be treated as an undirected graph). (20 points) Given a directed graph, describe an efficient algorithm for checking if there is a vertex v in the graph from which all other vertices are reachable. What is the order of growth of the running time of your algorithm in the worst case? (Note: inefficient algorithms will receive partial credit). (15 points) Connected Components (1) Consider the following modified version of class Graph for representing undirected graphs: class Graph int V: No. of vertices list int> *ady: // Each vertex belongs to a connected component in the graph. /1d[0] stores the id of the connected component vertex o belongs to, Wid[1] stores the component id for vertex 2, etc. Widtuj - idivl if and only if u and v belong to the same component int. id; public: Graph (int i) { this->V - V; adj - new listint>[V]; 1 -Graph() { delete I) ad)) void addEdge (int v, int w) adh tv).push_back(): adj[w]).push_back(v); 1 bool sameComponent(int , int w) { return id[v] - id (w): 1 ); A. Perform the following modifications so that function sameComponentiv, w) correctly returns true if vertices v and w are in the same component: a. Modify the constructor so that the array id is allocated with size V. Initialize the array such that each vertex in the graph is in a separate component. b. Modify function addEdge so that the components are updated (if necessary) each time a new edge is added. Example 0 0 1 0 2 2 3 3 4 3 0 0 1 0 WN 3 3 4 3 0 0 1 0 WN | 4 3 B. What is the order of growth of the running time of creating a complete graph using the addEdge function you have created? (25 points) Connected Components (2) Consider the following modified version of class Graph for representing undirected graphs: class Graph int V; // No. of vertices list int> *ady; // Each vertex belongs to a connected component in the graph. // id[0] stores the id of the connected component vertex 0 belongs to, Wid[11 stores the component id for vertex 1, etc. // id[u] -- id[v] if and only if u and v belong to the same component int* id; public: Graph (int V) this->V = V; adj = new list[V]: -Graph() / delete [1 adj; } void addEdge (int v, int w) adj [v].push_back(w); adj[w] .push_back (v); 2 bool connectedComponents() { } Implement function connectedComponents() such that it finds all the connected components in the graph, fills the array id and returns it. Note the following: You are not allowed to modify the constructor or function addEdge. All the computation must be done inside function connectedComponents or inside other functions called from within connectedcomponents. You are allowed to add private data members and private or public member functions as needed. . Function connectedcomponents must run in time that is at most linear in the graph size (i.e. O(E+V)