# What's the name of this DFS variation

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

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!

• I think there is an error here, why would you append v to heap (before the while loop). We should be only interested in the neighbors. Am I wrong? Jul 5, 2020 at 15:25
• so what do the lines for v in V do if v not in visited then append v to heap do ? Jul 5, 2020 at 17:16
• I see the issue. This solution is correct, but before the for loop we need to "expand" s (the only vertex in the heap). In fact, the for loop is only there to handle case where G is disconnected. Jul 5, 2020 at 17:37
• Moreover, assuming that the graph is connected, nothing prevents the algorithm from jumping from s to a node v that is not a neighbor of s. Another issue, at each step we recompute the priorities of all the accessible and not visited nodes rather than only considering the neighbors of some node. Jul 5, 2020 at 17:45
• I made a modification to my solution, but I want to make sure I'm understanding the problem correctly. We visit each vertex in this manner: 1) first visit s at time t=1, 2) next visit a neighbor of s with the maximum weight (call it v) at time t=2, 3) next visit a neighbor of s or v (that is not s or v) with the maximum weight at time t=3, etc. Is this the correct way to interpret the problem? Jul 5, 2020 at 18:39