前言

图这个数据结构相比队列、栈、树来说算是复杂多了，关于图的问题也多如牛毛，先来看一下常见的问题：

若无向图 G 中含7个顶点，要想保证图 G 在任何情况下都是连通的，则需要的边数最少是几条？

回答这种问题一定要注意细节，找到关键的点，不然一定会掉到坑里的。这个题关键点有以下几个：

• 7个顶点
• 任何条件下连通
• 最少几条边

其中第1点和第3点不容易出错，比较容易出现问题的是第2点，要想保证任何条件下连通，意思给定边数以后无论怎么连都能通？

先说下答案是16，至于为什么，我们后面先复习一下图相关的概念再慢慢解释，因为此刻的我连什么是强联通图都忘了~

一些概念

• 图：是由顶点V集和边E集构成，边表示了与之相连的两点间的关系，因此图可以表示成G = (V, E)
• 有向图：是指图中的两个顶点从A到B和从B到A的含义是不同的，我们认为两点的关系是有方向的，则称其为有向图
• 无向图：是指两点间的连接线无方向无关，这种图叫做无向图
• 连通性：从图中一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的
• 连通图：在无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图
• 完全图：在无向图中，如果任意两个顶点之间都边直接相连，则称此无向图为完全图
• 连通分量：若无向图不是连通图，但图中存在某个子图符合连通图的性质，则称该子图为连通分量
• 强连通图：在有向图中，若任意两个顶点之间包含至少来回两条通路，则称此有向图为强连通图
• 有向完全图：在有向图中，如果任意两个顶点之间都有相反的两条弧直接相连，则称此有向图为有向完全图
• 强连通分量：若有向图不是强连通图，但图中存在某个子图符合强连通图的性质，则称该子图为强连通分量

关于题目的解释

这是一个无向图，要想在任何情况下都连通，那考虑极端情况就是孤立一个顶点，让尽可能多的边连接剩余的顶点，那会构成一个 n-1 个顶点的完全图，然后再考虑加一条边把剩下的孤立顶点连起来，这样得到的边数是 N = 5+4+3+2+1 + 1 = 16，用组合数表示就是

$$C_{n-1}^2+1=(n-1)\ast (n-2)/2+1$$

题目变型

• 若无向图 G 中含7个顶点，要想保证图 G 在是连通的，至少需要几条边？

  答案6条，即 (n-1)

• 一个包含7个顶点的无向图 G 为完全图，那么它共有几条边？

  答案21条，即 n * (n-1) / 2

• 若有向图 G 中含7个顶点，要想保证图 G 在是强连通的，至少需要几条弧？

  答案7条，即 n，也就是形成一个环

• 一个包含7个顶点的有向图 G 为完全图，那么它共有几条弧？

  答案42条，即 n * (n-1)

补充两个图例

• 完全图，特点是任何两个顶点都有直接的边相连

• 强连通图，任意两点间都有路径可达

总结

• 解答关于图的问题可以从概念入手，更要注意题目中至多、至少、任何等字眼
• 弄清楚连通图、完全图、连通分量、强联通图、强连通分量等概念，迷糊的时候可以画一画
• 使用mermaid语法画的图确实不怎么好看，不过它强在了描述性的语言

那些看似漫不经心的成功，其实都是蓄谋已久；那些你以为的驾轻就熟，其实都是有备而来。一个人越活越好的样子应该是不沮当下，不弃未来。你要相信，所有的事与愿违或许都是惊喜的铺垫，所有的坚持不懈终将得到岁月的奖赏~