Home /
Expert Answers /
Computer Science /
1-given-a-directed-graph-g-v-e-and-two-vertices-u-and-v-in-v-we-call-vertex-v-is-reachable-fro-pa962
(Solved): 1. Given a directed graph G=(V,E), and two vertices u and v in V, we call vertex v is reachable fro ...
1. Given a directed graph G=(V,E), and two vertices u and v in V, we call vertex v is reachable from u, if there exists a directed path from u to v. A vertex s in V is called a source vertex if every vertex in V is reachable from s. (a) (10%) Given a directed graph G=(V,E), and a specified vertex v in V, design a linear time algorithm (i.e., your algorithm should run in O(∣V∣+∣E∣)-time) to determine if v is a source vertex. You need to describe the data structure used in your algorithm. (b) (15%) Given a directed acyclic graph G=(V,E), you are asked to determine if G contains a source vertex. If you apply the algorithm of the subproblem (a) on every vertex of G, you will get algorithm runs in O(∣V∣2+∣V∣∣E∣)-time. It is not desirable. Design a more efficient algorithm for this problem. Analyze the time complexity of your algorithm. (c) (15%) Given a directed graph G=(V,E), you are asked to deter mine if G contains a source vertex. Note that the given graph may contain directed cycles. As in subproblem (b) an O(∣V∣2+∣V∣∣E∣) - time algorithm is not acceptable. Design a more efficient algorithm for this problem. Analyze the time complexity of your algorithm.
ANSWERS and SOLUTIONS :(a) To determine if a vertex v is a source vertex, we can use a Depth-First Search (DFS) algorithm. The DFS algorithm will start from the vertex v and visit all reachable vertices. If all vertices in the graph are visited, then v is a source vertex.Pseudocode for the algorithm :Then, to check if v is a source vertex :The data structure used in this algorithm is an adjacency list to represent the graph, and an array to keep track of visited vertices. The time complexity of this algorithm is O(|V| + |E|) because each vertex and each edge is visited once.