Question

You are given a directed acyclic graph G(V,E), where each vertex v that has in-degree 0 has a value value(v) associated with it. For every other vertex u in V, define Pred(u) to be the set of vertices that have incoming edges to u. We now define value(u) = ?v∈P red(u) value(v). Design an O(n + m) time algorithm to compute value(u) for all vertices u where n denotes the number of vertices and m denotes the number of edges in G. You can assume that G is given to you in the adjacency-list representation.

Answer 1

Since the Graph is a DAG we can Topologically sort it.

and then add the value of nodes 'v' that do not have incoming edge to the nodes having edge from v.

Algorithm:

Topologically Sort G   

repeat until |G|>0

      find a vertex v having no incoming edge

      add its value to all vertices 'u' present in the adjacency list of v

     remove v

Time complexity : Topological sort takes O(m+n)

since the graph is already topologically sorted, finding vertex with no incoming edge takes O(1) time (it is the one with largest finishing time)

each vertex is removed once and same is with the edge so removal of verteices and edges take O(m+n) time. So total time taken is O(m+n)