Question

et G = (V, E) be a directed graph in which each vertex in u E V is labeled with a unique integer L(u) from the set {1, 2 ...,V]}. For each vertex u E V, let R(u) = {v E V: una v} be the set of vertices that are reachable from u (a node can always reach itself by default). Let min(u) be the vertex in R(u) with the minimum label, i.e. min(u) is vertex v such that L(v) is the smallest among all other nodes in R(u). Describe an O(V + E) time algorithm that computes min(u) for all vertices u € V,

Answer 1

Using knowledge in DFS algorithms it is possible to write code that can organize the vertices and create functions that understand the order of factors.

Writting in DFS algorithm

dfs(node)

{

mark node as visited

//initialize ans for this node to label of this node

ans=label[node]

for every neigbor of node

{

if the neighbor is visited

{

ans=minimum(ans,calculated[neighbor])

}

else if the neighbor is unvisited

{

call dfs(neighbor)

ans=minimum(ans,calculated[neighbor])

}

}

calculated[node]=ans

}

{

if the node is not visted{

call dfs(node)

}

}

for the given example graph we get minimum label for vertices as:

1 1 1 3 3 6 (in order for a,b,c,d,e,f), so the vertex with this label are c,c,c,e,e,f.

See more about DFS algorithm at brainly.com/question/13014003

#SPJ1