图的深度优先遍历 / 宽度优先遍历¶
前置知识¶
建图，递归，queue
目标¶
通过图上的遍历，形象的理解深度优先和宽度优先的区别。
图的深度优先遍历¶
Depth-first search and Breadth-first search. Both algorith
ms are given a starting node in the graph, and they visit all nodes that can be reached from the starting node. The difference in the algorithms is the order in which they visit the nodes. Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.
The neighbors of node 5 are 2 and 3, but the search has already visited both of them, so it is time to return to the previous nodes. Also the neighbors of nodes 3 and 2 have been visited, so we next move from node 1 to node 4
The time complexity of depth-first search is �(�+�) where n is the number of nodes and m is the number of edges, because the algorithm processes each node and edge once.
vector<int> adj[N];
bool visited[N];
void dfs(int s) {
if (visited[s]) return;
visited[s] = true;
// 遍历所有相邻的结点
for (auto u: adj[s])
dfs(u);
}
图的宽度优先遍历¶
Breadth-first search (BFS) visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search.
Like in depth-first search, the time complexity of breadth-first search is �(�+�) , where n is the number of nodes and m is the number of edges.
queue<int> q;
bool visited[N];
int distance[N];
visited[x] = true;
distance[x] = 0;
q.push(x);
while (!q.empty()) {
int s = q.front(); q.pop();
for (auto u : adj[s]) {
if (visited[u]) continue;
visited[u] = true;
distance[u] = distance[s]+1;
q.push(u);
}
}
题单¶
总结¶
利用图，我们可以直观的理解，在图上的深度优先遍历 / 宽度优先遍历的过程。
当然，在树上也是一样的。