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$, $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!

$\endgroup$
19
  • $\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$
    – Simone
    Jul 5 '20 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$
    – Simone
    Jul 5 '20 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$
    – tylerhx111
    Jul 5 '20 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$
    – Simone
    Jul 5 '20 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$
    – tylerhx111
    Jul 5 '20 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.