1

I'm just starting to look at understanding the graph data structure and the breadth first search and depth first search algorithms. For a package manager like npm, where one package might have dependencies and those dependencies might have more dependencies, if you wanted to check whether you had those dependencies already, is that a depth-first search?

Example:

  • I want to install package Top
  • Top has two dependencies, Middle1, and Middle2
  • Middle1 has one dependency, Bottom1, and Middle2 has one dependency, Bottom2

Now before I install Top, I want to check if I have Middle1, Bottom1, Middle2, Bottom2. Is that a depth-first search?

1

In a breadth-first search/iteration of a tree, you first visit all nodes on the current "level" in the tree before going to the next level. Visiting the packages in the order Top, Middle1, Middle2, Bottom1, Bottom2 would be a breadth-first iteration of the dependency tree.

In a depth-first search/iteration, you would follow a dependency link as soon as you encounter one. This would result in visiting the packages in the dependency tree in the order Top, Middle1, Bottom1, Middle2, Bottom2.

For walking a dependency tree and installing the missing dependencies, neither method of walking the tree is inherently better, as you need to visit all nodes anyway.

4

It doesn't matter. BFS vs DFS only changes the order of nodes visited (that's why it's called "depth/bread first", after all), it doesn't change the set of nodes. (Unless your tree is infinite, of course.)

Since you need to know the whole set of dependencies anyway to check them, it doesn't matter which way you go.

  • Nitpick: It changes the set of visited nodes iff you interrupt it. Visiting an infinite graph may take infinitely long, but "once you have finished" everything has been visited – Caleth Oct 2 '17 at 8:52
  • I agree. Method of tree searching is only relevant when tree is potentially unending or you only require a partial match. Finding a node in a tree might be relevant if you have reason to believe you'd find it closer to the root node (BFS) or at a leaf (DFS), but I don't think OP has reason to think one would be better than the other. – Neil Oct 2 '17 at 8:52

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.