深度优先搜索和广度优先搜索

在图论中图的遍历是非常常见的操作,两种图的遍历的经典方法:深度优先搜索和广度优先搜索。因为经常忘记其实现方法,这里特意写篇文章记录这两种方法的实现的关键点。可能会存在很多实现方法,这里只记录我知道而且觉得最好理解的方法。   

深度优先搜索

  深度优先搜索实现的一个关键的思想就是递归。   关键代码如下:

1
2
3
4
5
6
7
8
9
10
void dfs(int i){
cout<<i<<' '; //输出点i,代表访问这个点
visited[i]=1;
for(int j=0;j<n;j++)
//访问与点i有连接且还没访问的点
if( edge[i][j] == 1 && visited[j]==0 ){
dfs(j); //对访问的点再进行深搜
}
return ;
}

  完整代码如下:

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
27
28
29
30
31
#include <iostream>
using namespace std;

int edge[1000][1000] = { 0 };
int visited[1000] = { 0 };
int nodes;
int edges;

void dfs(int i){
cout << i << ' '; //输出点i,代表访问这个点
visited[i] = 1;
for (int j = 0; j<nodes; j++)
//访问与点i有连接且还没访问的点
if (edge[i][j] == 1 && visited[j] == 0){
dfs(j); //对访问的点再进行深搜
}
return;
}

int main(){
int s, d;
cin >> nodes >> edges;
for (int i = 0; i<edges; i++){
cin >> s >> d;
edge[s][d] = 1;
edge[d][s] = 1;
}
dfs(0);//从第0个点开始

return 0;
}

输入:

1
2
3
4
5
6
5 5
0 1
0 2
0 4
1 3
2 4
输出:
1
0 1 3 2 4 

广度优先搜索

  广度优先搜索实现的一个关键点是通过队列来存储访问过的点,并以队列里面的点作为始点访问其周围的点。   关键代码见下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> que; //存储已经访问过的点
int head=tail=0; //head表示当前所访问的点,tail表示最后一个点的后一个点
visited[0]=1;//从第0个点开始访问,访问过的点加入到队列中
que.push_back(0);
tail++;
while(head<tail){ //当head和tail相等时表示所有点已经访问过了
for(int i=0;i<nodes;i++){
int cur=que[head];//获取当前访问节点
//将与访问点距离为1且还没访问的点加入到队列中
if( edge[cur][i] == 1 && visited[i]==0 ){
que.push_back(i);
visited[i]=1;
tail++;
}
}
//访问完当前访问点周围的点,再访问下一个点
head++;
}
  完整代码见下所示:
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
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
using namespace std;
int main(){
int edge[100][100]={0};
int visited[100]={0};
int nodes,edges, s,d;
cin>>nodes>>edges;
for(int i=0;i<edges;i++){
cin>>s>>d;
edge[s][d]=1;
edge[d][s]=1;
}

vector<int> que; //存储已经访问过的点
int head=0,tail=0; //head表示当前所访问的点,tail表示最后一个点的后一个点
visited[0]=1;//从第0个点开始访问,访问过的点加入到队列中
que.push_back(0);
tail++;
while(head<tail){ //当head和tail相等时表示所有点已经访问过了
for(int i=0;i<nodes;i++){
int cur=que[head];
//将与访问点距离为1且还没访问的点加入到队列中
if( edge[cur][i] == 1 && visited[i]==0 ){
que.push_back(i);
visited[i]=1;
tail++;
}
}
//访问完当前访问点周围的点,再访问下一个点
head++;
}

for(int i=0;i<que.size();i++){
cout<<que[i]<<' ';
}

return 0;
}

输入:

1
2
3
4
5
6
5 5
0 1
0 2
0 4
1 3
2 4
输出:
1
0 1 2 4 3