What is the purpose of BFS and DFS?

Question

I found out how these algorithms work, but what are they used for?

Do we use them for:

• find some node in the graph or
• to find the shortest path or
• to find the loop in the graph

?

Both of them just visit all the nodes and mark their visit, and I see no reason to do this.

It is as if I have lost here what I am teaching.

Answer 1

BFS and DFS are graph search algorithms that can be used for various purposes.

One common use of the two search methods is to identify all nodes reachable from a given starting node. For example, suppose you have a collection of computers, each of which is connected to several other computers. Running BFS or DFS from the given node, you will find all other computers on the network with which the original computer can directly or indirectly talk. These are computers that return marked.

BFS can be used specifically to find the shortest path between two nodes in an unweighted graph. Suppose, for example, that you want to send a packet from one computer on a network to another and that the computers are not directly connected to each other. Which way should you send the package so that it can reach its destination as quickly as possible? If you start BFS and at each iteration each node stores a pointer to its "parent" node, you will eventually find the route from the beginning of the node to each other node in the graph, which minimizes the number of links that must be passed in order to reach the destination computer.

DFS is often used as a routine in more complex algorithms. For example, the Tarjan algorithm for calculating tightly coupled components is based on depth search. Many optimizing compiler methods run DFS on a suitably constructed chart to determine in which order to apply a particular series of operations. A depth search can also be used to generate a maze: by accepting a grid of nodes and linking each node to its neighbors, you can build a graph representing the grid. Performing a random depth search in this graph, he creates a labyrinth that has exactly one solution.

This is not a complete list. These algorithms have all kinds of applications, and when you start to learn more complex algorithms, you will often rely on DFS and BFS as building blocks. This is similar to sorting - sorting by itself is not so interesting, but the ability to sort a list of values ​​is extremely useful as a subroutine in more complex algorithms.

Hope this helps!