Write a pseudo code for a Graph algorithm

Given a DAG $$G=(V, E)$$ and a function $$f(v)$$ which maps every vertex to a unique number from 1 to $$|V|$$, I need to write a pseudo code for an algorithm that finds for every $$v\in V$$ the minimal value of $$f(u)$$, among all vertices $$u$$ that are reachable from $$v$$, and save it a an attribute of v. The time complexity of the algorithm needs to be $$O(V+E)$$ (assuming that time complexity of $$f(v)$$ is $$\Theta (1)$$).

I thought about using DFS (or a variation of it) and/or topological sort, but I don't know how to use it in order to solve this problem.

In addition, I need to think about an algorithm that gets an undirected graph and the function $$f(v)$$, and calculate the same thing for every vertex, and I don't know how to do it either.

• For a connected undirected graph, all vertices are reachable from every other vertex. So every vertex would have the same minimum reachable value right? Dec 13 '20 at 12:07

Yes, you can use the topological sort. Suppose topological sorting of the vertices gives you the sequence: $$v_{1}, \dotsc, v_{n}$$ such that there is no edge of the form $$(v_{j},v_{i})$$ for any $$i < j$$.

Following would be the pseudocode to compute the minimum reachable $$f(u)$$ value for each vertex $$v_{i} \in V$$:

fun()
----- int min_val_reachable[n];    // array that stores minimum reachable f(u) value for each vertex

----- for(i = n to 1; i--)
-------- min_val_reachable[i] = f(v_i) // since a vertex v_i is reachable to itself
-------- for each vertex 'u' in adj_list[v_i]
-------------- if (min_val_reachable[i] > min_val_reachable[u])
-------------------min_val_reachable[i] = min_val_reachable[u]
-------------- end
--------- end
----- end
----- return min_val_reachable[];

The time complexity of the topological sort is $$O(|V| + |E|)$$, and the time complexity of the above procedure is also $$O(|V| + |E|)$$. Thus, the overall complexity is $$O(|V| + |E|)$$.

You can prove the correctness of the above procedure using the induction technique as follows:

Hypothesis: After $$t$$ iterations of the outer "for loop", we get the correct min_value_reachable[] for every vertex from $$v_{n}$$ to $$v_{n-t+1}$$

Base Case: For $$t = 1$$, it is easy to see that min_value_reachable[$$v_n$$] = $$f(v_n)$$ since $$v_{n}$$ does not has any child, and $$v_{n}$$ is reachable to itself.

The induction case is also simple. Hope you can figure out the details yourself.

Given a vertex $$v$$, let $$F(v)$$ be the minimum value $$f(u)$$ among all nodes $$u$$ reachable from $$u$$ in the input DAG $$G=(V,E)$$.

Notice that a vertex $$u$$ is reachable from $$v$$ if and only if $$u=v$$ or $$u$$ is reachable from some out-neighbor $$w$$ of $$v$$. Then, we can write:

$$F(v) = \min\{ f(v), \min_{(v,w) \in E} F(w) \},$$ where the minimum of over an empty range is $$+\infty$$.

Let $$v_1, \dots, v_n$$ be the vertices of $$G$$ in reverse topological order, and notice that the previous equation for $$F(v_i)$$ only depends on $$f(v_i)$$ and on the values $$F(v_j)$$ with $$j.

If we compute $$F(v_1), F(v_2), \dots, F(v_n)$$ in this order, then we will only need time proportional to the out-degree $$\delta_i$$ of each $$v_i$$. More precisely, we will spend time $$O( 1 + \delta_i)$$ to compute $$F(v_i)$$. Since $$\sum_{i=1}^n ( 1 + \delta_i) = |V| + |E|$$, the overall time complexity is also $$O(|V| + |E|)$$.

If the graph $$G$$ is not a DAG then, the same approach works once you preprocess $$G$$ by identifying all the connected components $$C$$ into a single vertex $$v_C$$ having $$f(v_C) = \min_{u \in C} f(u)$$. This preprocessing requires time $$O(|V|+|E|)$$, since this is the time required to compute the connected components of $$G$$ (which are a partition of $$G$$). In particular this captures the case where $$G$$ is an undirected graph since it is equivalent to solving the problem using the directed version of $$G$$: just replace each undirected edge $$\{u, v\}$$ with the pair of directed edges $$(u,v)$$ and $$(v,u)$$.