列出连通集的邻接表解题

- 日理万妓 2022-01-05 18:47 229阅读 0赞

[列出连通集的邻接表解题][Link 1]

也许有许多人像我一样，一开始用邻接表做这题，结果发现深搜的顺序是错的导致这题出不来。很多人于是放弃了邻接表，利用邻接矩阵，显然方便很多。但我不信这个邪，咱就一起死磕这题！

先来看看为什么会错。其实你发现深搜是没有问题的，本来深搜就不是唯一的，所以我们的深搜和答案仅仅是顺序不一样而已。

那么答案的顺序是怎样的呢？题目中有“假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点”，显然是按序号从大到小访问顶点。

由于我们是临界表，各个顶点的连接关系可以看作是单链表来实现的，这就要求我们每个顶点后的单链表是递增排序。然鹅我们建立单链表的时候是读到两个顶点，利用前插法在这两个顶点后分别接上另一个顶点。显然输入不是按照递增顺序，这就导致我们为每个顶点建立的单链表不是递增，从而不能满足“按编号递增的顺序访问邻接点”。

好啦，明白问题后，我们想想解决方法。

既然是要死磕邻接表，那么这个存储结构就不变了。想要邻接表做到“按编号递增的顺序访问邻接点”，想来也不难，就是让每个顶点后的单链表按递增顺序排列。

最后一步，让单链表递增排列，那么就只有两种方法了：

1. 待单链表建立完后，对整个单链表进行排序

2. 在生成单链表的时候，按递增顺序确定插入结点位置后再插入

两种方法都行的，只是多写一个接口的问题。为了避免建立完链表后再对它进行一次循环，我选择了第二种方法。

**代码**

这是一开始的代码。我们只需注意深搜的接口即可，其余的作为解这题的参考。

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

1 #include <iostream>
      2 #include <queue>
      3 
      4 using namespace std;
      5 
      6 //采用邻接表，一下为定义
      7 typedef struct ArcNode {
      8     int adjvex;
      9     struct ArcNode *nextarc;
     10 }ArcNode;
     11 typedef struct VexNode {
     12     int data;
     13     struct ArcNode *firstarc;
     14 }VexNode,AdjList[10];
     15 typedef struct {
     16     AdjList vertices;
     17     int vexnum, arcnum;
     18 }ALGraph;
     19 
     20 //函数声明
     21 void Create(ALGraph &G);
     22 void DFS(ALGraph G, int v);
     23 void BFS(ALGraph G, int v);
     24 
     25 bool visited_DFS[10] = { false };
     26 bool visited_BFS[10] = { false };
     27 
     28 int main() {
     29     ALGraph graph;
     30     Create(graph);
     31     //输出深搜
     32     for (int i = 0; i < graph.vexnum; i++) {
     33         if (visited_DFS[i] == false) {
     34             cout << "{ ";
     35             DFS(graph, i);
     36             cout << "}" << endl;
     37         }
     38     }
     39     //输出广搜
     40     for (int i = 0; i < graph.vexnum; i++) {
     41         if (visited_BFS[i] == false) {
     42             cout << "{ ";
     43             BFS(graph, i);
     44             cout << "}" << endl;
     45         }
     46     }
     47     return 0;
     48 }
     49 
     50 //创建邻接表
     51 void Create(ALGraph &G) {
     52     int v1, v2;
     53     ArcNode *p1, *p2;
     54     cin >> G.vexnum >> G.arcnum;
     55     for (int i = 0; i < G.vexnum; i++) {
     56         G.vertices[i].data = i;
     57         G.vertices[i].firstarc = NULL;    //初始化为空，避免野指针
     58     }
     59     //两点确定一边，前插法
     60     for (int i = 0; i < G.arcnum; i++) {
     61         p1 = new ArcNode;
     62         p2 = new ArcNode;
     63         cin >> v1 >> v2;
     64         p1->adjvex = v2;
     65         p2->adjvex = v1;
     66         p1->nextarc = G.vertices[v1].firstarc;
     67         G.vertices[v1].firstarc = p1;
     68         p2->nextarc = G.vertices[v2].firstarc;
     69         G.vertices[v2].firstarc = p2;
     70     }
     71     //cout << "创建" << endl;
     72 }
     73 
     74 //深搜
     75 void DFS(ALGraph G, int v) {
     76     ArcNode *p = new ArcNode;
     77     int w = 0;
     78     cout << G.vertices[v].data << " ";
     79     visited_DFS[v] = true;
     80     p = G.vertices[v].firstarc;
     81     while (p != NULL) {
     82         w = p->adjvex;
     83         if (visited_DFS[w] == false) {
     84             DFS(G, w);
     85         }
     86         p = p->nextarc;
     87     }
     88 }
     89 
     90 //广搜,引入队列作为辅助
     91 void BFS(ALGraph G, int v) {
     92     queue<int> q;
     93     ArcNode *p = new ArcNode;
     94     int w = 0;
     95     cout << G.vertices[v].data << " ";
     96     visited_BFS[v] = true;
     97     q.push(v);
     98     while (!q.empty()) {
     99         v = q.front();
    100         q.pop();
    101         p = G.vertices[v].firstarc;
    102         while (p!=NULL) {
    103             w = p->adjvex;
    104             if (visited_BFS[w] == false) {
    105                 cout << G.vertices[w].data << " ";
    106                 visited_BFS[w] = true;
    107                 q.push(w);
    108             }
    109             p = p->nextarc;
    110         }
    111     }
    112 }

因为顺序不对过不了

![1494579-20190525154513489-2110204867.jpg][]

既然决定了要在插入的时候保持链表的升序，就写出以下接口

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

1 ArcNode* Insert(ArcNode *firstarc, ArcNode *p) {
     2     ArcNode *p1, *p2 = NULL;
     3     if (firstarc == NULL) {        //原链表为空
     4         firstarc = p;    
     5         p->nextarc = NULL;
     6         return firstarc;
     7     }
     8     p1 = firstarc;
     9     //定位到要插入的位置
    10     while ((p->adjvex > p1->adjvex) && p1->nextarc != NULL) {    
    11         p2 = p1;    //p2记住p1
    12         p1 = p1->nextarc;    //p1指向后一个结点
    13     }
    14     if (p->adjvex < p1->adjvex) {    //插在p1前
    15         p->nextarc = p1;
    16         if (firstarc == p1) {        //插在表头
    17             firstarc = p;
    18         }
    19         else {        //插在表中
    20             p2->nextarc = p;
    21         }
    22     }
    23     else {        //插在表尾
    24         p1->nextarc = p;
    25         p->nextarc = NULL;
    26     }
    27     return firstarc;
    28 }

升序插入的接口

最后，在建立链表的部分进行调整，注意这个部分前后的区别

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

1 //创建邻接表
     2 void Create(ALGraph &G) {
     3     int v1, v2;
     4     ArcNode *p1, *p2;
     5     cin >> G.vexnum >> G.arcnum;
     6     for (int i = 0; i < G.vexnum; i++) {
     7         G.vertices[i].data = i;
     8         G.vertices[i].firstarc = NULL;    //初始化为空，避免野指针
     9     }
    10     //两点确定一边，前插法
    11     for (int i = 0; i < G.arcnum; i++) {
    12         p1 = new ArcNode;
    13         p2 = new ArcNode;
    14         cin >> v1 >> v2;
    15         p1->adjvex = v2;
    16         p2->adjvex = v1;
    17         p1->nextarc = G.vertices[v1].firstarc;
    18         G.vertices[v1].firstarc = Insert(G.vertices[v1].firstarc, p1);    //原为G.vertices[v1].firstarc = p1;
    19         p2->nextarc = G.vertices[v2].firstarc;
    20         G.vertices[v2].firstarc = Insert(G.vertices[v2].firstarc, p2);    //原为G.vertices[v2].firstarc = p2;
    21     }
    22     //cout << "创建" << endl;
    23 }

修改创建邻接表的接口

![1494579-20190525154523463-1154078810.jpg][]

posted on 2019-05-25 15:40 [BlackDn][] 阅读( ...) 评论( ...) [编辑][Link 2] 收藏

转载于:https://www.cnblogs.com/luoyang0515/p/10922630.html

[Link 1]: https://www.cnblogs.com/luoyang0515/p/10922630.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/87031a0d73454624a01672a849ecb7a0.png
[1494579-20190525154513489-2110204867.jpg]: /images/20211228/a2c0bdb4acef4b9cbcb68f46c8f57baa.png
[1494579-20190525154523463-1154078810.jpg]: /images/20211228/65b6aa6c6c8a4698ab31082cfc3ac508.png
[BlackDn]: https://www.cnblogs.com/luoyang0515/
[Link 2]: https://i.cnblogs.com/EditPosts.aspx?postid=10922630