假设我们不会DFS和BFS,因为DFS和BFS本身就是图而来的。
补充一下,之前没有说清楚,无向图的本质是存储有向图。
有向有权图是图的存储的终极形式。
补充知识:C++11循环
c++11有增强for循环,可以这样遍历整个数组:
for (auto item : array)
{
cout << item << " ";
}
DFS
想一想为什么他叫DFS?因为DFS是deep first search,深度优先搜索!
他先搜索的深度,一条路走到黑再回头(~小朋友可不能学DFS一样一路走到黑哦~~)
如图现在我们需要用a~z的字母把他们4个格子填满,DFS会先填第一个并且考虑a然后在第一个为a的情况下考虑第二个。以此类推,当全部填满的时候就会回头考虑第四个填b。
这就是DFS:勇往直前,碰壁回头。
eg:跑路
我们混得不好准备跑路,需要从城市1跑路到终点城市n。
问能否成功跑路?
定义vis[x]表示x节点是否经过,vector <int> e[x]表示x城市的道路。
void dfs(int x) {
if(vis[x]) return;
vis[x] = 1;
if(x == n) // 成功跑到
ans = true;
for(int &p: e[x])
dfs(p); // 考虑从 x 能直接跑到的所有的 p,递归过去
}
这样我们就完成了图上DFS遍历!
DFS:深度第一!上面说得优先深度!
BFS: 广度第一!上面说得优先访问每一条边
BFS
BFS(breadth first search)顾名思义,广度优先搜索自然是广度第一。
优先搜索每一条边。
可以看到,搜完第1条直接搜索第二条,将第一条压入队列,搜完第一层再取出。所以dfs是一层一层的搜索的。
eg:跑路
没错,又是我!
说明不必再提。
BFS需要队列来存储搜到哪.
还是和刚刚一样,定义vis[x]表示x节点是否经过,vector <int> e[x]表示x城市的道路。
void bfs() {
queue <int> q; // STL 容器有二次内存分配机制
// 把起点加进队列
q.push(1);
while(!q.empty()) {
int now = q.front();
q.pop();
// 取出队首,访问
if(vis[now]) continue; // 防止重复访问
vis[now] = 1;
if(now == n) {
puts("Yes");
return;
}
for(int &p: e[now]) // 把相邻的点丢进队列
q.push(p);
}
puts("No");
}
这样我们就完成了图上BFS!
This post was written on August 17, 2022.