The difference between BFS and DFS

Question

I read about DFS in an introduction to Cormen algorithms. Below is the text code snippet.

Unlike BFS, whose subgraph predecessor forms a tree, the subgrpah predecessor created by DFS can consist of several trees, because the search can be repeated from several sources.

In addition to the above notes, the following is mentioned.

It may seem arbitrary that BFS is limited to only one source, where as DFS can search from multiple sources. Although conceptually BFS can come from dissimilar sources, and DFS can be limited to one source, our approach reflects how the results of these searches are commonly used.

My question

• Can I give an example of using BFS with multiple sources and DFS is used with a single source?

Answer 1

When he talks about several sources, this means the start of a node search. You will notice that the parameters of the algorithms are BFS(G, s) and DFS(G) . This should already be a hint that BFS is one source, and DFS is not, because DFS does not accept the starting node as an argument.

The main difference between the two, the authors note, is that the result of BFS is always a tree, while DFS can be a forest (collection of trees). This means that if BFS is launched from node s, then it will build a tree of only those nodes that can be accessed from s, but if there are other nodes in the graph, they will not touch them. However, DFS will continue to search the entire schedule and build a forest of all these connected components. This, as they explain, the desired result of each algorithm in most cases of use.

As the authors note, there is nothing that could stop small changes to create a single DFS source. Actually this change is easy. We just accept another parameter s , and in the DFS routine (not DFS_VISIT ) instead of lines 5-7, iterating over all the nodes in the graph, we just do DFS_VISIT(s) .

Similarly, modifying a BFS allows you to run it from multiple sources. I found an implementation online: http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html , although this is slightly different from another possible implementation that automatically creates separate trees. The meaning of this algorithm is: BFS(G, s) (where s is the set of nodes), while you can implement BFS(G) and automatically create separate trees. This is a small change in line, and I will leave it as an exercise.

According to the authors, the reason why they were not fulfilled is that the main use of each algorithm gives them usefulness in the form in which they are. While this is well done to reflect on this, this is an important point to be understood.

Answer 2

Do you understand the definition? Have you seen some photos in the holy book?

When it is said that DFS can consist of several trees, this is because it goes deeper until it reaches the leaf and then back. So basically imagine a tree, first you look for the left subtree, and then the right subtree. the left auxiliary tree may contain several hypochondria. That's why.

When you think about BFS, it is level based. first level search in other words. therefore, you have a single source (node) than you are viewing all sub-elements of this level.

DFS with a single source if there is only one child node, so you only have one source. I think it would be more clear if you take the source as the parent node.