CODEWITHSUNDEEP
algorithmdata-structuresgraphdirected-acyclic-graphs
fortm
fortm

Reputation: 4208

find longest paths for each node in a dag from start node

enter image description here

Using a modified BFS, we can find this by re-visiting the node if found a path longer than seen so far. For ex - D -> G would mark G as visited with sequence = 3 (seq of D) + 1 = 4. but while visiting F -> G, a longer path is found which will give new sequence of G = 4 (seq of F ) + 1 = 5

Finally, if in a hashmap,last sequence is saved for each node in below implementation, the highest one can be obtained. But this requires re-visiting nodes. Also topological sort using DFS won't work here since it might give an order and sequence like this -> A -> C -> E -> F -> B -> D -> G -> H , but infact , B & C should get same sequence as they have similar dependency structure.

public void bfsWithLevel(Vertex<T> root)
{
 Queue<Vertex<T>> queue = new LinkedList<>();
 root.setVisited(true);
 queue.add(root);
 root.setSequence(1);
 while (!queue.isEmpty())
 {
 Vertex<T> actualVertex = queue.remove();
 log.info(actualVertex + " ");

 for (Vertex<T> v : actualVertex.getAdjacencyList())
 {
 if (!v.isVisited() || v.getSequence() < actualVertex.getSequence() + 1)
 {
 v.setSequence(actualVertex.getSequence() + 1);
 v.setVisited(true);
 queue.add(v);
 }
 }
 }
}

Looking for an optimal solution to avoid revisiting and a linear time solution for a dag like above without any cycles.

Upvotes: 0

Views: 330

Answers (1)

user58697
user58697

Reputation: 7923

You face revisiting because you push v as soon as it has been discovered. Instead, you may postpone it, and only push it when all incoming links has been traversed, along the lines of:

    for (Vertex<T> v : actualVertex.getAdjacencyList())
    {
        if (v.getSequence() < actualVertex.getSequence() + 1)
        {
            v.setSequence(actualVertex.getSequence() + 1);
        }
        v.incoming--;
        if (v.incoming == 0) {
            q.add(v);
        }
    }

Of course, for that to work the graph shall be preprocessed, to compute the number of incoming links for each node. It is yet another (regular) BFS scan, but the total time remains linear.

Upvotes: 1

Related Questions