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

发表于 标签 ， ，

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

深度优先搜索

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

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
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;  
}  
```  
输入:  
```  
5 5  
0 1  
0 2  
0 4  
1 3  
2 4  
```  
输出：  
```  
0 1 3 2 4

广度优先搜索

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

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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++;  
}  
```  
　　完整代码见下所示：  
```cpp  
#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
7
8
9
10
5 5  
0 1  
0 2  
0 4  
1 3  
2 4  
```  
输出：  
```  
0 1 2 4 3