【数据结构周周练】028 图的存储及遍历经典习题

古城微笑少年丶 2021-06-11 15:13 389阅读 0赞

上次是第一次分享非算法类题目，不知道大家有没有认真去思考，今天继续给大家分享几道比较经典的图的存储及遍历的题目，希望大家能够先自己做，然后再看我的分析。也希望大家能够喜欢。

## 例题1 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][]

**【分析】**（1）要正确区分无向图和有向图度的问题，无向图中，一个顶点的度 = 该点相连接的边的条数 = 第i个链表中结点个数。

（2）、（3）邻接表与邻接矩阵各有优缺点，操作简单是针对不同的操作，不能笼统说哪个更为简单，应该说在哪个方面，哪个更为简单，所以（2）、（3）均不对。

（4）有向图的结点的度 = 该结点的入度 + 该结点的出度，求结点的入度，需要遍历除该结点外的整个邻接表，求结点的出度，需要遍历该结点的邻接结点，所以需要遍历整个邻接表。

综上，只有（2）正确。

## 例题2 ##

![20181111213827444.png][]

**【分析】**想要弄明白这道题，就要明白什么时候会调用DFS函数，我们在遍历过程中调用两次DFS函数，分别是DFSTraverse函数调用，以及DFS函数进行递归调用。DFS进行递归调用时，访问的是所有的连通部分，即一个连通分量的所有结点会通过DFS遍历调用完成，而DFSTraverse函数是开始一个未调用结点，每进行一次DFSTraverse函数调用，说明本次为开始遍历图或上一次DFSTraverse调用结束，一次DFS就会访问一个连通分量，所以在DFSTraverse中DFS个数与连通分量的个数相同。

## 例题3 ##

![20181111214945934.png][]

**【分析】**

【易错选项】（2）首先先说一下这道题大家审题不细致会错选（2），因为大家知道通过DFS遍历无环有向图是进行拓扑有序的过程，就会选择（2）。

【正确结论】但是大家一定要注意一个细节，就是在退出递归时才输出相应顶点，得到的顶点序列是输出的，所以我们会得到的是输出的顺序，输出的顺序和遍历顺序相反，所以得到的是逆拓扑有序，选择（1）。

## 例题4 ##

![20181111220659740.png][]

**【分析】**错。我们知道**图的连通分量不仅仅是指图的连通的分量，更重要的是其极大连通子图，要求的是极大的概念**，所以，如果一个图G有环的话，则其连通分量一定有环，那G1就可能有环，而生成树是不能有环的，这个时候，就不是G的连通分量了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/8abbb1b5ec7044b0a3654a25c612d4b9.png
[20181111213827444.png]: /images/20210516/53ead9ca8c6347a9a300f7596ed4458f.png
[20181111214945934.png]: /images/20210516/541ed1e45f674fe4a0e622c3f7e74824.png
[20181111220659740.png]: /images/20210516/0ca41d3999284fb0bceb324886dad3a0.png