DFS和BFS简单总结

总结

这两个是图的基本算法,很简单。

转载一下别人的总结
版权声明:本文为CSDN博主「EbowTang」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/EbowTang/article/details/44263635

DFS的思想是一条路走到底,走不到底就回到上个状态点。

  1. 如果可能,访问一个邻接的未访问顶点,标记它,并把它放入栈中。
  2. 当不能执行规则1时,如果栈不空,就从栈中弹出一个顶点。(返回上一个顶点)
  3. 如果不能执行规则1和规则2,就完成了整个搜索过程。

伪代码:

1
2
3
4
5
6
7
8
9
10
{
mark v as visited //标记顶点为已访问
for each w adjacent to v //将邻顶点变成新的当前顶点
{
if w unvisited//若这个新的当前节点没有被访问过
{
dfs(w) //递归调用
}
}
}

广度优先搜索较之深度优先搜索之不同在于,深度优先搜索旨在不管有多少条岔路,先一条路走到底,不成功就返回上一个路口然后就选择下一条岔路,而广度优先搜索旨在面临一个路口时,把所有的岔路口都记下来,然后选择其中一个进入,然后将它的分路情况记录下来,然后再返回来进入另外一个岔路,并重复这样的操作。

  1. 访问下一个未来访问的邻接点,这个顶点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
  2. 如果因为已经没有未访问顶点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
  3. 如果因为队列为空而不能执行规则2,则搜索结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
{
create a queue Q //创建一个队列
enqueue s onto Q //顶点s进队
mark s as visited //
while Q is not empty
{
dequeue a vertex from Q into v //将Q中顶点v弹出
for each w adjacent to v //v的每个邻接点w
{
if w unvisited //w未访问过
{
mark w as visited //标记w已范围
enqueue w onto Q //w入栈
}
}
}
}

实战

有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,…,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初,除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true,否则返回 false。

示例 1:

输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。
示例 2:

输入:[[1,3],[3,0,1],[2],[0]]
输出:false
解释:我们不能进入 2 号房间。
提示:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/keys-and-rooms
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

BFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
_rooms = rooms;
rooms_len = _rooms.size();
int rooms_visited[rooms_len]={0}; //if the room was visited, set is to 1;
unlocked.push_back(1);
BFS(0,rooms_visited); //use BFS
return rooms_len==unlocked.size();
}
void BFS(int index, int rooms_visited[]){
rooms_visited[index] = 1;
vector<int> it = _rooms[index];
vector<int>::iterator sit;
for(sit=(it).begin();sit!=(it).end();sit++){
if(rooms_visited[*sit]!=1){
unlocked.push_back(1);
BFS(*sit,rooms_visited); //search it
}
}
}
private:
vector<vector<int>> _rooms;
vector<int> unlocked;
int rooms_len;
};

DFS:(不好意思,上面的是DFS。。。BFS如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
queue<int> point; //顶点队列
point.push(0); //初始点入队列
int roo = 1; //总room数量,需等于rooms.size()表示可全部访问
int is_visited[rooms.size()] = {0};
is_visited[point.front()] = 1;
while(point.size()!=0){
vector<int> new_room = rooms[point.front()]; //取出待搜新房间
point.pop(); //弹出队列第一个顶点
vector<int>::iterator it;
for(it=new_room.begin();it!=new_room.end();it++){
if(is_visited[*it]!=1){ //未搜
point.push(*it); //入队列等待搜取
is_visited[*it] = 1;
roo++; //开的房间加1
}
}
}
return roo == rooms.size();
}
};
Author

lyq1996

Posted on

2020-02-20

Updated on

2022-06-05

Licensed under

Comments