1
$\begingroup$

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). Example

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

$\endgroup$
2
$\begingroup$

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$, $s \in V$ is the start vertex, and $w(j,t)$ is the weight function taking a vertex $j \in V$ and a timestep $t$.

BestFirstTraversal(G=(V,E), s, w(j,t))
    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
    
    while heap is not empty 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-t_init:])  # 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)$.

The while loop runs $n$ times since the graph is connected and all nodes will be expanded. 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!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joffrey L. Jul 5 at 15:25
  • $\begingroup$ so what do the lines for v in V do if v not in visited then append v to heap do ? $\endgroup$ – Joffrey L. Jul 5 at 17:16
  • $\begingroup$ 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. $\endgroup$ – Tyler Hughes Jul 5 at 17:37
  • $\begingroup$ 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. $\endgroup$ – Joffrey L. Jul 5 at 17:45
  • $\begingroup$ 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? $\endgroup$ – Tyler Hughes Jul 5 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.