What's the name of this DFS variation

Question

Classical DFS:

A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS is usually used to find an ordering of the tasks that satisfies all of the precedence constraints, classical DFS algorithm can do it by building the sequence step by step.

An extension:

Consider now the following variation. Each node $j$ is weighted by a value $w_j$. When we are currently at node $j$, this weight will determine the next node to visit (the one with the higher weight).

Moreover, imagine that each time a node is added to the list, we recompute the weight for the unvisited nodes using a given function (we don't care about the nodes that has already been added to the sequence). Thus at step $t$, the $w_j(t)$ of node $j$ can be different from its weight at step $t+1$.

---

Questions: Is there a name of this problem ? How to solve it efficiently? (e.g If a node has several successors, one needs to determine the successor with highest weight, so which data structure to use?)

N.B The image is only used for an illustration purpose. The graph is not assumed to be a binary tree.

Edit: the graph is assumed to be connected

Answer 1

This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function w. This strategy uses a priority queue (e.g. a heap, in this case a max heap).

Consider the following algorithm. $G=(V,E)$ is a graph with vertex set $V$ and edge set $E$, $w(j,t)$ is the weight function taking a vertex $j \in V$ and a timestep $t$, and $S \subseteq V$ is the list of start vertices (one in each connected component of $G$). $G$ is not necessarily connected.

BestFirstTraversal(G=(V,E), w(j,t), S)
    visited = []
    t = 0
    
    # from [0, t):   heap is the order in which the vertices are visited
    # from [t, end]: heap is a max heap
    heap = S  # from t to the end is max heap
    
    # loop until all vertices have been visited
    while len(visited) != |V| do
        u = heap[t]  # get the max element
        
        # do something with u
        
        append u to visited
        append neighbors of u (not in visited) to heap
        t = t+1
        
        heapify(heap[t:])  # based on w at step t
    end while
end

Let $n = |V|$ be the number of vertices.

Run Time: BestFirstTraversal runs in $O(n^2)$.

Notice $S$ is a list of vertices, one for each connected component of $G$. This is necessary because there must be a starting point for each connected component. If we started from a single node in a graph with more than one connected component, we would never be able to visit the other connected components. Thus the loop will visit each node in $G$ from one of the starting vertices.

Thus the while loop runs $n$ times. Appending neighbors and heapify takes up to $O(n)$ work. Hence, $n * (2 * O(n)) = O(n^2)$.

Note, heap will contain the order of the vertices visited at the end BestFirstTraversal.

Hope that helps!