Learning Deep DFS and Wide BFS Search Algorithms

---

Two ways of traversing a graph:

1. Depth First Traversal (DFS - Depth First Search)
2. Breadth First Traversal (BFS - Breath First Search)

The graph traversal algorithm, which handles temporary data, relies on two abstract data structures:

• a wooden or bamboo pen for sheep or cattle
• formation

Breadth-first dynamic graphs

The breadth-first traversal, also called hierarchical traversal, traverses the first layer (node 1), then the second layer (nodes 2, 3, 4), the third layer (5, 6, 7, 8), and the fourth layer (9, 10).

Depth-first dynamic diagrams

From the root node, has been to the left child node until the left child node does not exist and then return to the last node to go to the node's right child node, and then all the way to the right child node to go, the same also can not go so far on the return. Obviously this way all the way to the black, black on the way back, is the process of depth-first traversal.

Specific steps for breadth and depth

In breadth search, storing the lower level data requires the use of a queue, the
In deep search, storing the data for an entire path requires the use of a stack , which is used to backtrack to the very beginning of the vertex.
For specific steps go to "Algorithms in Seconds: Interpreting Data Structures with Common Sense", I think the book breaks it down in enough detail that I don't need to move it around once.

Depth and breadth of application scenarios

I've had quite a few interviews and many of the interview questions have slowly faded away, but one has stuck with me:
He asked, do you usually use depth or breadth when you're doing a crawl?

In retrospect, I think it's bullshit that he asked.

Why?

The choice of depth or breadth corresponds to different scenarios. All problems, theoretically, can be solved with lists, but why do we need to differentiate so many data structures?

It's not because--For different problems, different data structures are used so that the solution is efficient and resources are saved.

For example, look at this family structure chart below this one:

If you want to find all the sons and daughters of great-grandmother Ruby, use depth or breadth?

• Definitely breadth is best.
  Using a breadth-first search, then all of her direct daughters (Andrea, Xander, CoCo, and Maya) are found immediately, without having to search for relatives a generation removed from her.

If you want to find a descendant of Ruby called Ruth, use depth or breadth?

• Obviously the depth is appropriate.
  With a depth-first search, you can then immediately move to the bottom of the graph and find the great-grandchildren generation within a few steps.
  It still requires traversing the entire graph to find Ruth, but at least finding her quickly is possible. With a breadth-first search, on the other hand, there's no choice; you have to traverse everyone in the first two generations before you can start searching the great-grandchildren's generation.

When thinking about whether to use depth or breadth, you should be thinking about whether you want to search as close to the initial vertex as possible first, or whether you want to search as far away from it as possible first.

• The former is suitable for searching with breadth-first
• The latter is suitable for searching with depth-first search.