【数据结构周周练】027 图的基本概念及存储经典习题

迷南。 2021-06-11 15:13 410阅读 0赞

有人跟我私聊说能不能分享一些算法以外的练习题呢？毕竟数据结构不仅仅是代码。我觉得他说的对，前段时间刚刚开始分享有关于图的内容，但是由于刚刚开始，不宜出难度太大的题，分享的代码比较少，所以，这些练习题呢，我们先从图分享开始。希望大家能够喜欢。

今天给大家分享的是几道比较经典的题目，希望大家能够先自己做，然后再看我的分析。

## 例题1 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][] 例题1

**【分析】**（1）所有顶点有入度，出度，且无向图的所有顶点的入度之和等于出度之和，即所有顶点的度之和为偶数。

（2）边数还可以等于顶点个数-1，比如三个顶点，两条边的链，也是无向连通图，无向连通图的最小生成树还是无向连通图，且边数都等于顶点个数-1；错误。

（3）如果是三个顶点三条边的环，没有度为1的顶点。

综上，只有（1）正确。

## 例题2 ##

![20181109233226403.png][] 例题2

**【分析】**保证任何情况下都连通，就要保证最坏的情况，即所有的边，保证6个顶点都互相有边，这样就算把所有的边都给这六个顶点，那我们还会有多余的边，来保证剩下顶点的连通，即保证6个顶点两两相互有连接，并保证至少还有一条连接第七个顶点，即至少需要：6 × 5 ÷ 2 + 1 = 16 条边。

## 例题3 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1][] 例题3

**【分析】**因为任何顶点u对应的边表都是存放以u为起点的所对应的另一个顶点v。从而v在边表中出现的次数是它的入度。这里一定要注意边表是后面的部分，注意和定点表的区分。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/3b85d3d57f74418ebd5ad64c519d8996.png
[20181109233226403.png]: /images/20210516/63b710fab99940908d230c8da1d8fc1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1]: /images/20210516/a71ddae02d7b46aebe2d1623731c0b62.png