图结构的 DFS-BFS 遍历
Summary in One Sentence
Graph traversal is an extension of multi-way tree traversal. The main traversal methods are Depth-First Search (DFS) and Breadth-First Search (BFS). The only difference is that trees do not have cycles, whereas graphs might have cycles. Thus, we need to mark visited nodes to prevent the traversal function from getting stuck in an infinite loop.
Specifically, when traversing all "nodes" in a graph, we use a visited array to mark nodes in the pre-order position. When traversing all "paths" in a graph, we use an onPath array to mark nodes in the pre-order position and unmark them in the post-order position.
If the problem states that the graph has no cycles, then graph traversal is exactly the same as multi-way tree traversal.
Next, let me explain the above summary with examples.