Compare advantages and disadvantages of DFS and BFS and name vocabulary

dfs and bfs Use adjacency table and adjacency matrix to store graph , The time complexity is O(N E) and O(N2), If you traverse the entire graph , The space complexity is O(N) If you already know that the dissociation root node is closer , that BFS Better If each node has many edges as a whole , that BFS It will consume a lot of memory If a tree is very deep and has few answers , that DFS It could be very slow （ On the contrary, if the solutions are many and deep , that BFS It's going to be slow ） If a problem has infinite depth and limited breadth , that DFS You can't get a solution , but BFS Sure , On the contrary, the same is true

One , connected ： Connectivity is from the vertex V To W There is an undirected path , said V and W It's connected .

Two , Connected component ： The polar Tongzi graph of undirected graph .
Two characteristics of connected components
1. The maximum number of vertices ： Add another one to the current graph and it will no longer be connected .
2. Maximum number of sides ： Contains all edges connected to all vertices in the subgraph .（ All included edges of all vertices are in ）

3、 ... and , loop
The path from the beginning to the end .

Four , Connected graph
All vertices in a graph are connected .

5、 ... and , Strong connectivity 、 Weakly connected
In a directed graph, vertices V and W There is a two-way path between , said V and W It's strongly connected .

6、 ... and , Strongly connected graph
Vertices of any quantity in a directed graph are strongly connected

7、 ... and , Strong connected components
Maximal strongly connected graphs of directed graphs

One call at a time DFS（x）/BFS（x） Are all the x Traversal of the connected component . So what if a graph is not connected , We'll do the required... Once for all the points we haven't visited DFS（x）/BFS（x）, You can traverse all the points of the graph .

Pay attention to the time complexity , If you have any N vertices E side . The time complexity of adjacency table storage graph is O（N+E）, The time complexity of adjacency matrix is O（N²）;