I want to find independent nodes of each node of a DAG. The easiest way to do so is visiting predecessors and successors and removing from the set. However, this approach takes a long time if there are a lot of nodes. What would be the best way to find independent nodes?
Independent Nodes: If you can't visit a node by using either predecessors or successors of the current node without switching (using either predecessors or successors), they are independent. (See the example)
Example:
- For A:
{E} - For G:
{B, C} - For D:
{}
Well i don't think that there is another way of doing it but anyways even if you visiting all the nodes once complexity wouldn't be more than O(nodes) for finding independent nodes wrt to one node , you can use BFS for this approach.