第六章学习小结

骑猪看日落 2021-12-13 20:29 419阅读 0赞

题目：

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第1行给出2个整数N(0)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:

按照”{ v​1​​ v​2​​ … v​k​​ }“的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

  1. 8 6
  2. 0 7
  3. 0 1
  4. 2 0
  5. 4 1
  6. 2 4
  7. 3 5

输出样例:

  1. { 0 1 4 2 7 }
  2. { 3 5 }
  3. { 6 }
  4. { 0 1 2 7 4 }
  5. { 3 5 }
  6. { 6 }
  9. 心得体会： 这道题的解题思路还是比较清晰的 即对于两个遍历的运用 解决这道题的思路是： ①建立起一个图并且填充 ②完成DFS遍历 ③完成BFS遍历 ① 根据题意可以选择以邻接矩阵的数据结构来建立图 首先是根据题意定义一个图的结构体
  11. struct graph
  12. {
  14.     int arcs[mvnum][mvnum];//邻接矩阵
  15.     int vexnum, arcnum;//顶点数 边数
  16. };
  18. 然后是图的填充
  20. void creategraph(graph &g)
  21. {
  22.     cin >> g.vexnum >> g.arcnum;//输入顶点与边数
  23.     int a, b;//端点编号
  24.     for (int i = 0; i < g.arcnum; ++i)
  25.     {
  26.         cin >> a >> b;//输入相连的端点编号
  27.         g.arcs[a][b] = g.arcs[b][a] = 1;//在邻接矩阵中将两端点状态赋值为相连
  28.     }
  29. }

②

DFS遍历

首先是定义一个访问数组

  1. bool visited[mvnum];//访问数组
  3.  然后为完成遍历连通图部分
  5. void dfs(graph g, int v)
  6. {
  7.     cout << " "<<v; //输出当前访问端点编号
  8.     visited[v] = true; //将其作为访问数组下标，赋值其状态为已访问
  9.     for (int i = 0; i < g.vexnum; ++i)
  10.     {
  11.         {
  12.             if (!visited[i] && g.arcs[v][i] == 1)//若该端点编号i未被访问过，且其与当前所访问端点v相连
  13.             {
  14.                 dfs(g,i);//利用递归，访问端点i（下一层）
  15.             }
  16.         }
  17.     }
  18. }

最后为完成非连通图部分

  1. void dfss(graph g)
  2. {
  3.     for (int j = 0; j < g.vexnum; ++j)
  4.     {
  5.         if (!visited[j])//若有端点未被访问
  6.         {
  7.             cout << "{
  8.      ";
  9.             dfs(g, j);
  10.             cout << " }"<<endl;
  11.         }
  12.     }
  13. }

③

BFS遍历

首先还是定义一个访问数组

  1. bool visit[mvnum];

然后为完成遍历连通图部分

  1. void bfs(graph g,int v)
  2. {
  3.     int x;//队头元素
  4.     cout << " " << v; //输出当前访问端点编号
  5.     visit[v] = 1; //将其作为访问数组下标，赋值其状态为已访问
  6.     queue<int> q; //存放端点编号队列
  7.     q.push(v);//v入队
  8.     while(!q.empty()) //当队列为空时结束循环
  9.     {
  10.         x = q.front();//取队头元素
  11.         q.pop();//队头元素出队
  12.         for (int i = 0; i < g.vexnum; ++i)
  13.         {
  14.             if (!visit[i] && g.arcs[x][i] == 1)//若该端点编号i未被访问过，且其与当前所访问端点x相连
  15.             {
  16.                 cout << " "<<i;
  17.                 visit[i] = 1; //将其作为访问数组下标，赋值其状态为已访问
  18.                 q.push(i); //将其压入队列
  20.             }
  21.         }
  23.     }
  24. }

最后最后为完成非连通图部分

  1. void bfss(graph g)
  2. {
  3.     for (int i = 0; i < g.vexnum; ++i)
  4.     {
  6.         if (!visit[i])//若有端点未被访问
  7.         {
  8.             cout << "{
  9.      ";
  10.             bfs(g, i);
  11.             cout << " }" << endl;
  12.         }
  13.     }
  14. }

需要注意的地方：

弄清循环条件，究竟是图的边数还是顶点数

  1. 目标完成情况：
  3. 与之前相比，找出入手点能力有所提高
  5. 目标：
  7. 提高对“图”方面知识的认识与理解，并能运用

转载于:https://www.cnblogs.com/Berlins/p/10891387.html

发表评论

表情：
评论列表 （有 0 条评论，419人围观）

还没有评论，来说两句吧...

相关阅读

    相关 第六章

    1.目录管理的主要功能：按名存取；提高检索速度；文件共享；允许文件重名。 2.在索引节点中设置连接引用（links）计数的目的是为了实现目录管理的文件共享功能。 3.实现“

    以你之姓@以你之姓@/ 0 赞/ 478 阅读

    相关 第六章学习小结

    本章学习了图，图这种数据结构相对树的数据结构，又是复杂了许多，这一章图的作业是分别用深度搜索DFS和BFS广度搜索来输出非连通分量。抛开具体的存储结构，整个程序主要由三部分组成

    超、凢脫俗超、凢脫俗/ 0 赞/ 385 阅读

    相关 第四章学习小结

    第四章学习了串和数组的相关内容，以及学习了BF算法和KMP算法。这周上机课老师带着我们打了AI核心代码。 看到题目就觉得要求好多代码肯定很难写，听到老师说这道题目会有很多的边

    小鱼儿小鱼儿/ 0 赞/ 377 阅读

    相关 第六章学习小结

    题目： 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序

    骑猪看日落骑猪看日落/ 0 赞/ 420 阅读

    相关 第七章学习小结

    一、本章内容小结： 本章主要学习了查找的基本概念以及对于基于不同的数据结构的各种查找表适用的查找方法的定义、查找及算法，其中主要包括3种不同结构的查找表：线性表、树表和散列表

    布满荆棘的人生布满荆棘的人生/ 0 赞/ 466 阅读