I. Let G = (V,E) be a directed graph in which each vertex u E V is labeled with
ID: 3872942 • Letter: I
Question
I. Let G = (V,E) be a directed graph in which each vertex u E V is labeled with a unique integer L(u) from the set (1,2,., VI. For each vertex u E V, let R(u) be the set of vertices that are reachable from u. Define min(u) to be the vertex in R(u) whose label is minimum. (a) (10 pts) Write pseudocode for algorithm that computes min(u) for all vertices in the graph. You will receive a 5 pt extra credit if your algorithm runs in 0(lvl+ ED- (b) (10 pts) Prove the worst-case running time of your algorithm (c) Extra credit (10 pts): Prove that your algorithm is correct (i.e., that it will always output the correct answer).Explanation / Answer
The given graph G = (V,E)
For every vertex v in G Mark v undiscovered, erase the littlest label vertex in every part C.
This vertex be denoted by w(C).
For every edge (u,v) with u not within the C add a footing (u,w).
V in C of edge(u,v) and u not a footing (w,u)
The result Graph is computed in O(V+E)
In the graph each vertex has min(u) = u.
For every vertex min(u) = min(u,v)
If we tend to retrieve the vertices of (u,v) of u can have already found min(v).
To traverse the graph in BFS or DFS therefore we want to travel with the incoming vertices with their labels.
To calculate the Graph G^T that is that the same as G however with the direction of each edges reverted. This graph are often simply computed in linear time O(V + E). Then
Perform Reverse-DFS from v.
for each undiscovered vertex u we tend to encounter on this DFS:
DFS(v)
That is, rst perform BFS(1);
this may visit all vertices approachable from one in G^T (that is, which might reach one in G) So min(u) = 1
Then nd ensuing smallest nodethat has not been reached within the previous BFS and begin BFS from it, and so on.
This in total takes O(V ) to type the vertices (using a linear-time sorting algrithm)