Graph traversal (BFS & DFS basis)

Preface

We talked about graph storage before , The ultimate goal of the graph is to traverse , What are the ways of traversal , Let's break it down one by one .
（ Recognition and storage of graphs ：https://blog.csdn.net/weixin_42178241/article/details/125931691?spm=1001.2014.3001.5501）

Graph traversal

solve the problem

Like solving the problem of graph theory search , It can spread to multiple points , But our computer uses linear storage , And this kind of problem is nonlinear , We need to transform nonlinear problems into linear .

BFS

Breadth first search

The main idea

Traversal by hierarchy , The starting point level is 0, Its child nodes are 1, Its grandson node is 2, Pay attention to the marked nodes , Not in tag

nature

The new node that is traversed for the first time , The corresponding level is the shortest legal path from the starting point to the node

Code thinking

1. Input
2. initialization
3. The queue is not empty 4 5, Empty execution 6
4. Pop up the team head element , If you jump to 6
5. Expand the new node to execute 3
6. Output

DFS

Depth-first search

The main idea

One way to the dark , Traverse in turn according to the route , Can't go back to the last node .

Code thinking

1. Input
2. initialization
3. Traverse the starting node
4. Traverse the child nodes respectively
5. Node backtracking
6. Output

evolution

Some topics are in the opposite direction array , Some changes , There are also great changes to the conditions of the map , There are two solutions ：

1. A new node
2. Increase the dimension

summary

BFS

The main features

queue

solve the problem

1. The shortest path of multiple lines at the same point

DFS

The main features

Stack

solve the problem

1. Path process
2. Number of paths

Postscript

These knowledge BFS&&DFS The basis of , We will talk about the more difficult later .