第六章作业（1）

- 日理万妓 2021-12-01 16:10 393阅读 0赞

7-1 列出连通集 (30 分)

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

### 输入格式: ###

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

### 输出格式: ###

按照"\{ v1v2 ... vk \}"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

### 输入样例: ###

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

### 输出样例: ###

{ 0 1 4 2 7 }
    { 3 5 }
    { 6 }
    { 0 1 2 7 4 }
    { 3 5 }
    { 6 }
    
    根据老师日常引导的方法--我们先从主函数讲起

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int main()//首先先从大方向开始掌握思路，于是先打主函数 
     2 {
     3     ALGraph G; //由题知是由图来完成，那么应该先创建一张图 
     4     
     5     createUDG(g) ;// 生成图 
     6      
     7     for(int i=0;i<G.vex;i++) 
     8         sort(G,i);//根据每一个顶点进行排序，从而更好地进行匹配
     9     
    10     //排序后进行深搜+广搜
    11     
    12     //深搜     
    13     for(int i=0;i<G.vex;i++)
    14     {
    15         if(vi[i]==false)//循环输出呐~~ 
    16         {
    17             cout<<"{
             ";
    18             DFS(G,i);
    19             cout<<"}"<<endl;
    20         }
    21     }
    22  
    23     //转变vi数组 后才能进行广搜
    24     for(int i=0;i<Max;i++)
    25         vi[i]=false;
    26         
    27     //开始进行广搜
    28     for(int i=0;i<G.vex;i++)
    29         {
    30             if(vi[i]==false)//此处类似深搜的一段代码，原因就是都是循环输出哒~ 
    31             {
    32             cout<<"{
             ";
    33             BFS(G,i);
    34             cout<<"}"<<endl;
    35         }
    36          } 
    37     
    38 return 0;
    39 }

然后就开始一步步补充我们的主函数挖的坑啦~~

首先是ALGraph定义

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 typedef struct
    2 {
            //图的定义 
    3     int vex, arc;//图的顶点数量和边的数量 
    4     adjList vertices;//生成顶点列表  
    5 }ALGraph；

好的，那么我们又给自己挖了一个坑，既然是坑就得补上，AdjList邻接表类型

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 typedef struct VNode{
            //顶点列表的定义 
    2     int data;//留给数据的一个空间 
    3     struct ArcNode *firstArc;//这个顶点的第一条边的指针 
    4 }VNode,AdjList[Max]; //AdjList表示邻接表类型

得，又挖了一个坑，但是应该是图的最后一个啦~

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 typedef struct ArcNode{
            //由顶点列表推出来的边节点定义 
    2     int adjvex;//当前结点的顶点位置 
    3     struct ArcNode *nextArc;//指向下一条边的指针 
    4 }ArcNode,*L;

接着就是生成图的函数啦createUDG(G)~

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 void createUDG(ALGraph &G)
     2 {
     3     cin >> G.vex >>G.arc;//输入顶点和节点 分别的总数~ 
     4     for(int i=0;i<G.vex;i++)
     5     {
     6         G.vertices[i].data = i;
     7         G.vertices[i].firstArc = NULL;
     8     }
     9     int v1,v2;//一条边的两个顶点 
    10     L p1,p2;
    11     for(int i=0;i<G.arc;i++)
    12     {
    13         cin >> v1 >> v2;//对顶点V1处理，将V2加入到链表中
    14          p1 = new ArcNode;
    15          p1 -> adjvex = v2;
    16          p1 -> nextArc = G.vertices[v1].firstArc;
    17          G.vertices[v1].firstArc = p1;
    18          
    19          //        对顶点v2处理，将v1加入到链表中 
    20         p2 = new ArcNode;
    21         p2 -> adjvex = v1;
    22         p2 -> nextArc = G.vertices[v2].firstArc;
    23         G.vertices[v2].firstArc = p2;    
    24         
    25     }
    26 }

接着就是排序的--采用冒泡排序。。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 void sort(ALGraph G,int v)
     2 {
            //一种冒泡排序法，对于顶点的边的点进行排序，参考了大佬的排序 
     3     L i,j;
     4     int k;
     5     for(i=G.vertices[v].firstArc;i!=NULL;i=i->nextArc)
     6         for(j=G.vertices[v].firstArc;j->nextArc!=NULL;j=j->nextArc)
     7             if(j->adjvex > j->nextArc->adjvex)
     8             {
     9                 k = j->adjvex;
    10                 j->adjvex = j->nextArc->adjvex;
    11                 j->nextArc->adjvex = k;
    12             }    
    13 }

那么接下来就是最后的，额，深搜与广搜了

首先弄一个

//判断是否访问过的数组  
bool vi\[Max\] = \{false\};

接着就是深搜了：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //开始深搜的函数
     2 void(ALGrap G,int v) 
     3  {
     4      //访问当前的结点
     5      cout<<" "<<v;
     6      vi[v] = true;
     7      L p;//与顶点连接的下一个边
     8      
     9      int w;//与顶点连接的下一个点
    10      
    11      p = G.vertices.firstArc; 
    12      while(p!=NULL)
    13      {
            //取得这一条边连接的点，看看是否已经被访问过 
    14          w = p->adjvex;
    15          if(!vi[w])
    16              DFS(G,w);
    17         p = p->nextArc; 
    18      }
    19  }

接着就是广搜了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1  //广度搜索
     2 void BFS(ALGraph G, int v)
     3 {
            //队列q,u用作存储出队的元素的下标
     4     queue<int> q;
     5     int u;
     6     //访问顶点
     7     cout<<" "<<v;
     8     vi[v] = true;
     9     //入队
    10     q.push(v);
    11     while(!=q.empty())
    12     {
    13         u = q.front();
    14         q.pop();
    15         
    16         //for 循环， 进行出队元素的所有的边的点访问，入队
    17         for(L p=G.vertices[u].firstArc; p!=NULL ; p=p->nextArc)
    18         {
            //对于出队的点，判断是否有邻接点，有就访问，然后入队
    19             if(!vi[p->adjvex])
    20             {
    21                 cout<<" "<<p->adjvex;
    22                 vi[p->adjvex] = true;
    23                 q.push(p->adjvex);
    24              } 
    25             
    26          } 
    27      } 
    28     
    29  }

就这样就整个就完成啦~~

可惜就是通不过.........

还是需要修改，格式错误---记录一篇错误的博客。

下面才是真正的全部代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
      2 #include <queue>
      3 #define Max 20 //最大顶点数
      4 using namespace std;
      5 
      6 
      7 typedef struct ArcNode{
            //由顶点列表推出来的边节点定义 
      8     int adjvex;//当前结点的顶点位置 
      9     struct ArcNode *nextArc;//指向下一条边的指针 
     10 }ArcNode,*L;
     11 
     12 typedef struct VNode{
            //顶点列表的定义 
     13     int data;//留给数据的一个空间 
     14     struct ArcNode *firstArc;//这个顶点的第一条边的指针 
     15 }VNode,AdjList[Max]; //AdjList表示邻接表类型
     16 
     17 typedef struct{
            //图的定义 
     18     int vex, arc;//图的顶点数量和边的数量 
     19     AdjList vertices;//生成顶点列表  
     20 }ALGraph;
     21 
     22 void createUDG(ALGraph &G)
     23 {
     24     cin >> G.vex >>G.arc;//输入顶点和节点 分别的总数~ 
     25     for(int i=0;i<G.vex;i++)
     26     {
     27         G.vertices[i].data = i;
     28         G.vertices[i].firstArc = NULL;
     29     }
     30     int v1,v2;//一条边的两个顶点 
     31     L p1,p2;
     32     for(int i=0;i<G.arc;i++)
     33     {
     34         cin >> v1 >> v2;//对顶点V1处理，将V2加入到链表中
     35          p1 = new ArcNode;
     36          p1 -> adjvex = v2;
     37          p1 -> nextArc = G.vertices[v1].firstArc;
     38          G.vertices[v1].firstArc = p1;
     39          
     40          //        对顶点v2处理，将v1加入到链表中 
     41         p2 = new ArcNode;
     42         p2 -> adjvex = v1;
     43         p2 -> nextArc = G.vertices[v2].firstArc;
     44         G.vertices[v2].firstArc = p2;    
     45         
     46     }
     47 }
     48 
     49 void sort(ALGraph G,int v)
     50 {
            //一种冒泡排序法，对于顶点的边的点进行排序，参考了大佬的排序 
     51     L i,j;
     52     int k;
     53     for(i=G.vertices[v].firstArc;i!=NULL;i=i->nextArc)
     54         for(j=G.vertices[v].firstArc;j->nextArc!=NULL;j=j->nextArc)
     55             if(j->adjvex > j->nextArc->adjvex)
     56             {
     57                 k = j->adjvex;
     58                 j->adjvex = j->nextArc->adjvex;
     59                 j->nextArc->adjvex = k;
     60             }    
     61 }
     62 
     63 //判断是否访问过的数组 
     64 bool vi[Max] = {
            false};
     65 
     66 //开始深搜的函数
     67 void DFS(ALGraph G,int v) 
     68  {
     69      //访问当前的结点
     70      cout<<" "<<v;
     71      vi[v] = true;
     72      L p;//与顶点连接的下一个边
     73      
     74      int w;//与顶点连接的下一个点
     75      
     76      p = G.vertices[v].firstArc; 
     77      while(p!=NULL)
     78      {
            //取得这一条边连接的点，看看是否已经被访问过 
     79          w = p->adjvex;
     80          if(!vi[w])
     81              DFS(G,w);
     82         p = p->nextArc; 
     83      }
     84  }
     85  
     86  //广度搜索
     87 void BFS(ALGraph G, int v)
     88 {
            //队列q,u用作存储出队的元素的下标
     89     queue<int> q;
     90     int u;
     91     //访问顶点
     92     cout<<" "<< v;
     93     vi[v] = true;
     94     //入队
     95     q.push(v);
     96     while(!q.empty())
     97     {
     98         u = q.front();
     99         q.pop();
    100         
    101         //for 循环， 进行出队元素的所有的边的点访问，入队
    102         for(L p=G.vertices[u].firstArc; p!=NULL ; p=p->nextArc)
    103         {
            //对于出队的点，判断是否有邻接点，有就访问，然后入队
    104             if(!vi[p->adjvex])
    105             {
    106                 cout<<" "<<p->adjvex;
    107                 vi[p->adjvex] = true;
    108                 q.push(p->adjvex);
    109              } 
    110             
    111          } 
    112      } 
    113     
    114  } 
    115  
    116 
    117 int main()//首先先从大方向开始掌握思路，于是先打主函数 
    118 {
    119     ALGraph G; //由题知是由图来完成，那么应该先创建一张图 
    120     
    121     createUDG(G) ;// 生成图 
    122      
    123     for(int i=0;i<G.vex;i++) 
    124         sort(G,i);//根据每一个顶点进行排序，从而更好地进行匹配
    125     
    126     //排序后进行深搜+广搜
    127     
    128     //深搜     
    129     for(int i=0;i<G.vex;i++)
    130     {
    131         if(vi[i]==false)//循环输出呐~~ 
    132         {
    133             cout<<"{
             ";
    134             DFS(G,i);
    135             cout<<" "<<"}"<<endl;
    136         }
    137     }
    138  
    139     //转变vi数组 后才能进行广搜
    140     for(int i=0;i<Max;i++)
    141         vi[i]=false;
    142         
    143     //开始进行广搜
    144     for(int i=0;i<G.vex;i++)
    145         {
    146             if(vi[i]==false)//此处类似深搜的一段代码，原因就是都是循环输出哒~ 
    147             {
    148             cout<<"{
             ";
    149             BFS(G,i);
    150             cout<<" "<<"}"<<endl;
    151         }
    152          } 
    153     
    154 return 0;
    155 }

我真棒！

转载于:https://www.cnblogs.com/JeffKing11/p/10923481.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211201/a914e0c692e946e0932b11bfc91b9fc7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，393人围观）

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

相关阅读

相关 PTA第六章作业详解

PTA作业第六章

水深无声/ 2024年04月24日 23:20/ 0 赞/ 78 阅读

相关第六章作业

小灰灰/ 2022年08月01日 11:27/ 0 赞/ 219 阅读

相关第八章作业

第八章作业

傷城~/ 2022年08月01日 11:27/ 0 赞/ 299 阅读

相关第七章作业

第七章作业 1、

系统管理员/ 2022年08月01日 01:21/ 0 赞/ 287 阅读

相关第五章作业

![Center][] 第五章

╰半夏微凉°/ 2022年08月01日 01:20/ 0 赞/ 323 阅读

相关第六章

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

以你之姓@/ 2022年06月17日 03:46/ 0 赞/ 345 阅读

相关第六周作业

一.作业头文件这个作业属于那个课程 C语言程序设计II 这个作业要求在哪里 [https://edu.cnblogs.com/campus/zswxy/compute

ゝ一世哀愁。/ 2021年12月19日 17:53/ 0 赞/ 352 阅读

相关第六周作业

2019年春季第六次作业 <table> <thead> <tr> <th>这个作业属于哪个课程</th> <th style="text-al

桃扇骨/ 2021年12月15日 09:45/ 0 赞/ 399 阅读

相关第六章作业（1）

7-1 列出连通集 (30 分) 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的

- 日理万妓/ 2021年12月01日 16:10/ 0 赞/ 394 阅读

相关第六次作业

1. 概述 Selenium 测试直接在浏览器中运行，就像真实用户所做的一样。Selenium 测试可以在 Windows、Linux 和 Macint

Myth丶恋晨/ 2021年11月26日 10:36/ 0 赞/ 371 阅读