| 1)前言: |
前几个大佬写的题解我的大都看了一遍, 邻接表实现, 非递归实现真的不错, 非常适合想多学一些的同学们, 有助于扩展思维. 然后有一点要注意:有几个题解书写的代码没有考虑非连通图, 但是本题的测试用例依然通过了, 这里给出我的朴素代码(AC), 希望大家以后遇到非连通图的时候不要慌 |
| 2)解题思路: |
a:定义 一维数组作为访问标记数组标记第I个节点是否被访问过, 要初始化为false(在有些题中要定义二维数组) 二位数组作为图的邻接矩阵(建议开成全局的, 可以开的规模更大) b:函数 Init_matrix()初始化图(不想多说) DFS(int v)深度优先搜索 (PS:上面这几个东西是最基本的, 要记住!!) c:DFS思路 主函数中 在访问标记数组里面每一个元素的下标对应图中的一个节点序号 遍历访问标记数组(这里就可以防止出现连通分量未被访问的情况, 一旦一次递归结束还有节点未访问, 这个循环会找到一个新的未被访问的新节点作为下一次递归的开始) 挨个找到未被访问的节点 调用DFS(形参传递当前节点的序号); DFS(int now)中 访问now节点(在这里就可以对当前节点做出一些操作, eg:赋值, 带回值啊什么的, 具体看题) 标记成已经访问 在邻接矩阵中找到所有与该节点有关系且未访问的节点(与字前面代表循环, 后面是判断条件) 调用DFS(i); |
| 3)参考代码: |
1. #include <bits/stdc++.h>
2. #define maxv 50
3. #define _for(i,v,n) for(int i = v;i<n ; i++)
4. using namespace std;
5.
6. int n;
7. int record = 0;
8. int _map[maxv + 5][maxv + 5];
9. bool visited[maxv];
10.
11. void Init_matrix() {
12. _for(i, 0, n)
13. _for(j, 0, n)
14. scanf_s("%d", &_map[i][j]);
15. }
16. void DFS(int now) {
17. visited[now] = true;
18. record++;
19. printf("%d%s", now, record == n ? "\n" : " ");
20. _for(i, 0, n)
21. if (!visited[i] && _map[now][i])
22. DFS(i);
23. return;
24. }
25.
26. int main() {
27. scanf_s("%d", &n);
28. memset(_map, 0, sizeof(_map)); memset(visited, false, sizeof(visited));
29. Init_matrix();
30. _for(i, 0, n)//遍历visited数组 //防止出现连通分量
31. if (!visited[i]) DFS(i);
32. return 0;
33. }
34. /*
35.
36. */
37.
38. /*
39. 0 1 0 1 0
40. 1 0 0 0 0
41. 0 0 0 1 0
42. 1 0 1 0 0
43. 0 0 0 0 0
44. */ |
| (PS:在word排了十多分钟格式, 这里竟然不兼容 555555555) |
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复