第六章学习小结

超、凢脫俗 2022-01-06 09:19 402阅读 0赞

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

  1. void DFS_AM(AMGraph &G,int v)
  2.  {  //邻接矩阵的深度搜索 
  3.      for(int w=0;w<G.vexnum;w++)
  4.      if(G.arcs[v][w]!=0 && (!visited[w]) )
  5.      {
  6.      visited[w]=true;     //每访问一个就要将其置为true 
  7.      cout << w << " ";
  8.      DFS_AM(G,w);
  9.  }
  10. }

　　

  1. void BFS_AM(AMGraph &G,int v)
  2.  {
  3.      visited[v]=1;
  4.      queue<int> q;
  5.      int u;
  6.      q.push(v);
  7.     while(!q.empty())
  8.      {
  9.      u=q.front();
  10.     q.pop();
  11.      cout<< u << " ";
  13.     for(int w=0;w<G.vexnum;w++)
  14.     {
  15.         if(G.arcs[u][w]!=0 && (!visited[w]))
  16.         {
  17.             visited[w]=1;
  18.             q.push(w);
  19.         }
  20.     }
  21.      }

在作业题我们可以看到，我采用的存储结构是邻接矩阵，因为在进行对矩阵的两个顶点的边进行初始化时双向边用数组操作较为方便，如果用链式存储，对于指针的操作时十分复杂的。

还有关于图的应用，经过老师上课的分析在对图的最小生成树，最短路径的应用中，我们需要掌握算法思想，以及需要用到的辅助结构，包括它们的初态和终态，这三个算法核心思想十分相似，这为我们以后的解题提供了新思路。

转载于:https://www.cnblogs.com/liusiling/p/10889637.html

发表评论

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

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

相关阅读

    相关 第六章

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

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

    相关 第六章学习小结

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

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

    相关 第四章学习小结

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

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

    相关 第六章学习小结

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

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

    相关 第七章学习小结

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

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